춤추는 나무
Dancing tree | 이 기사는 대부분 또는 전체적으로 단일 출처에 의존하고 있습니다.: 나무 · · · · JSTOR ( 2021년 3월) |
컴퓨터 과학에서 춤추는 트리는 B+ 트리와 유사한 트리 데이터 구조입니다.레이저4 파일 시스템에서 사용하기 위해 한스 라이저에 의해 발명되었습니다.항상 노드의 균형을 유지하려고 시도하는 자가 밸런싱 바이너리 검색 트리와 달리 춤추는 트리는 데이터를 디스크에 플러시할 때만 노드의 균형을 조정합니다(메모리 제약 또는 트랜잭션 완료).[1]
이 배경에는 트리의 최적화를 지연시키고 필요할 때만 디스크에 쓰기함으로써 파일 시스템 운영 속도를 높이는 것이 있습니다. 이는 디스크에 쓰는 속도가 메모리에 쓰는 속도보다 수천 배 느리기 때문입니다.또한 이 최적화는 다른 트리 데이터 구조보다 덜 자주 수행되기 때문에 최적화는 더 광범위할 수 있습니다.
어떤 의미에서 이것은 느린 미디어 상의 스토리지에 최적화된 자가 밸런싱 바이너리 검색 트리로 간주할 수 있습니다.즉, 온디스크 폼은 항상 균형을 유지하지만 트랜잭션 도중의 기입은 이루어지지 않습니다.이렇게 하면 트랜잭션 중에 노드를 추가하거나 제거하는 것이 어려워집니다.대신, 이러한 느린 재조정 작업은 저장 매체에 훨씬 느린 쓰기 작업과 동시에 수행됩니다.
단, 예기치 않은 셧다운, 불완전한 데이터 쓰기 및 최종 균형 트랜잭션이 완료되지 않을 수 있는 기타 발생 시 이 동작의 부정적인 부작용이 나타납니다.일반적으로 댄싱 트리는 불완전한 트랜잭션에서 데이터를 복구하는 데 있어 기존 트리보다 더 큰 어려움을 야기하지만, 이는 트랜잭션된 데이터를 더 철저하게 고려함으로써 해결할 수 있습니다.
레퍼런스
- ^ Hans Reiser. "Reiser4 release notes - Dancing Tree". Archived from the original on 2007-10-24. Retrieved 2009-07-22.
