#6-2-4 The Art of Computer Programming - 정렬과 검색

이번 절은 다중 트리에 대한 내용이다.

지금까지 논의한 트리는 기본적으로 내부 검색을 위해서,

다시 말해 테이블 전체가 컴퓨터의 고속 내부 메모리(램 등)에 들어가 있는 상황을 위해서 개발되었다.

 

이제는 디스크나 드럼 등의 직접 접근 저장소에 들어있는 아주 큰 파일들에서 정보를 조회하기 위한

외부 검색에 사용되는 방법을 알아보도록 한다.

 

노드들을 페이지별로 만들면 이진트리가 8진 트리로 변한다. 페이지를 더 크게 잡으면 디스크는 2번만 접근하면 된다.

 

다중 트리 분기를 수단으로 한느 새로운 외부 접근 방식은 B트리를 이용하는데, B트리는 다음과 같은 성질들을 만족한다.

1. 모든 노드는 최대 m개의 자식들을 가진다.

2. 루트와 리프들을 제외한 모든 노드는 적어도 m/2개의 자식들을 가진다.

3. 루트는 적어도 두 개의 자식들을 가진다. (루트 자신이 리프가 아닌 한)

4. 모든 리프는 같은 수준에 나타나며, 정보는 담지 않는다.

5. 리프가 아닌 한 노드의 자식들이 k개 일 때, 그 노드는 k-1개의 키들을 담는다.

(리프는 자식이 없는 말단 노드를 의미)

 

B트리의 개선형이 B+트리, 그것을 또 개선해서 B*트리가 있다.

B트리의 전략을 조금 더 발전시킨 것이 SB트리이다.