6장. 인덱스 구조 / 7장. 인덱스된 순차 화일 - B트리

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+트리 사용