[데이터베이스/Database] B+ 트리(Balance Tree)

한 노드의 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 큰 값으로 정렬되어 있음.

내부 노드: 인덱스 엔트리. 키값과 방향 지시자로 구성.

리프 노드: 데이터 엔트리(검색 키 값으로 정렬됨)

검색 과정: 루트 노드(메인 메모리에 상주)에서 검색 시작 -> 검색 값에 따라 해당 자식 노드로 분기 -> Leaf 노드에 도달하여 탐색 레코드를 찾음.

 

 

 

B+ 트리 (Balanced tree in height)

- 루트 노드에서 리프 노드로 가는 모든 경로의 길이가 동일한 인덱스 구조

- 탐색 키 값에 관계없이 검색 시간이 거의 일정

- 검색을 위한 디스크 IO 횟수는 root로부터 leaf에 도달하는 경로의 길이

- 모든 리프 노드들은 double linked list로 연결됨

- 범위 검색에 유용

- 범용적인 인덱스 구조

- 모든 검색(SELECT)과 INSERT/DELETE/UPDATE에 좋은 성능을 가짐

- 리프 노드가 정렬된 검색 키 값으로 배열됨

 

 

Fan-out: 내부노드에 대한 자식들의 평균 수

Fan-out: n, height: h -> leaf node ≒ n^h

 

ex) n = 100, h = 4 -> Leaf = 100^4 = 1억

약 1억 개의 단말 노드들 중 4번의 입출력으로 탐색하여 원하는 페이지를 찾을 수 있으므로 매우 효율적.