위 에서 언급 된 문제 를 해결 하 기 위해 , KVS 트리 및 대응 하 는 동작 이 본 명세서 에 설명 된다 . KVS 트리 는 트리 의 내용 이 아니 라 키 의 미리 결정 된 유도 에 기초 하 여 부모 와 자식 사이 에 연결 을 갖 는 노드 를 포함 하 는 트리 데이터 구조 이 다 . 노드 는 키 - 값 세트 ( kvset ) 의 시간 정렬 된 시퀀스 를 포함 한다 . kvset 는 키 정렬 된 구조 의 키 - 값 쌍 을 포함 한다 . Kvset 는 또한 한 번 기록 되 면 불변 ( immutable ) 이 다 . KVS 트리 는 kvset 를 효율 적 으로 탐색 할 수 있 도록 kvset 를 노드 에 유지 하 고 kvset 는 정렬 된 키 뿐 만 아니 라 , 일례 에서 , 키 메트 릭 ( key metric ) ( 예 를 들 어 , 블룸 필터 ( bloom filter ) , 최소 및 최대 키 등 ) 을 포함 함 으로써 WB 트리 탐색 을 개선 하 면서 WB 트리 의 기록 처리 량 을 달성 한다 . 많 은 예 에서 , KVS 트리 는 값 으로부터 키 를 분리 하 고 더 작 은 kvset 집합 을 병합 함 으로써 LSM 트리 의 임시 저장 문제 를 개선 할 수 있 다 . 추가 적 으로 , 설명 된 KVS 트리 는 kvset 에 다양 한 유지 관리 동작 을 통해 기록 증폭 을 줄일 수 있 다 . 또한 노드 내 kvset 는 불변 이 므로 SSD 에서 기록 마모 와 같 은 문제 는 데이터 구조 에 의해 관리 되 어 , 디바이스 자체 의 가비지 수집 활동 을 줄일 수 있 다 . 이 는 내부 디바이스 자원 ( 예 를 들 어 , 버스 대역폭 , 처리 사이클 등 ) 을 확보 하 여 외부 드라이브 성능 ( 예 를 들 어 , 판독 또는 기록 속도 ) 을 향상 시키 는 추가 된 장점 을 제공 한다 . KVS 트리 및 이 트리 에 대한 동작 의 추가 상세 와 예시 적 인 구 현예 는 아래 에 설명 된다 .