CS Stack Exchange에 이런 질문을 올렸습니다. 하지만 여기서도 묻고 싶습니다. 어쩌면 저를 도와줄 수 있는 Linux 전문가가 있을지도 모릅니다!
Reiser4 파일 시스템에서 사용되는 춤추는 트리 데이터 구조를 누군가 명확하게 설명할 수 있다면 매우 감사하겠습니다. 이것은 제가 선택한 데모 주제이지만 이에 대한 리소스가 거의 없는 것 같습니다. 내가 찾을 수 있는 유일한 것은:
Reiser4의 Dancing Tree에 대한 설명:http://web.archive.org/web/20071024001500/http://www.namesys.com/v4/v4.html#dancing_tree
춤추는 나무 검색 작업:http://www.cofault.com/2006/03/reiser4-1-internal-tree.html
나는 이미 Dancing Trees의 기본 아이디어를 이해하고 있습니다. 내가 아는 한, 그것은 B+ 트리와 매우 유사하다. 하지만 삽입과 삭제 작업이 어떻게 수행되는지 추측할 수 있는 방법은 다음과 같습니다.
삽입은 B+ 트리의 삽입처럼 동작합니다(삽입 및 분할 가능).
삭제 작업은 항목을 제거하지만 트리가 수정될 때마다 최적화를 수행하고 싶지 않기 때문에 항목이 언더플로우(?)인 경우 병합하지 않습니다.
세 번째 질문은 다음과 같습니다. Dancing Tree는 디스크에 쓰기 전에 실제로 어떻게 "압착" 작업을 수행합니까? (Reiser4 설명에서도 언급했듯이)
누구든지 이것에 대해 밝힐 수 있다면 매우 감사하겠습니다! 지금 당장은 매우 혼란스럽기 때문에 약간의 설명이 필요합니다.