6장. 물리적 데이터베이스 설계 : 인덱스 관련
B 트리
- 이진트리 (binary search tree) (2-원 탐색 트리) 의 단점?
- 한쪽으로 편향되는 경우 탐색이 오래걸린다.
- 분기율(branching factor)이 2로 너무 낮아 트리가 너무 높아지고 탐색 경로가 길어질 수 있다.
- B 트리?
- B 트리의 B는 Balance로, 균형 트리다.
- m-원 탐색 트리로 분기율 선택 가능.
3차 B-트리
- 특징
- leaf node 뿐만 아니라 중간 node에도 모두 데이터 레코드의 주소를 저장.
- 따라서 순차 탐색 하는 경우 중위 순회 해야 함. 순차 탐색 성능 나쁨.
- 반면 최상위 node가 가리키는 데이터 레코드는 빠르게 접근 가능.
B+ 트리
- 즉 B트리와 B+트리의 가장 큰 차이는 B+트리는 leaf node만 데이터 레코드 주소를 가지고 있다는 것이다.
- Index set & Sequence set로 구성
- Index set : leaf node가 아닌 중간 노드. 키 값과 노드 포인터 보유
- Sequence set : leaf node. 키 값과 데이터 레코드 주소 보유
- B 트리의 느린 순차 탐색 보완
- 데이터 레코드 주소가 leaf node에만 존재하고, leaf node 끼리 linked list로 연결해두었기 때문에, 순차 탐색 시 상위 node로 올라갈 필요 없이 leaf node에서 link를 따라 쭉 읽으면 됨.
- 반면 B 트리는 상위 node에도 데이터 레코드 주소가 존재하기 때문에 상위 node를 왔다 갔다 하면서 탐색해야 함.
- 대부분의 다단계 인덱스는 B+트리 사용
