1. B 트리 (B-Tree, Balanced Tree)
ㅇ 이진 탐색 트리를 보다 일반화시킨 트리 자료구조를 말함
- 데이터베이스 및 파일시스템에 널리 쓰이는 자료구조
ㅇ 성능 및 공간 활용을 위해, 이진 탐색 트리에 제약조건을 부가시켜 확장한 것
- 트리가 항상 균형을 유지 (Balanced)
. 루트(root)와 리프(leaf) 간의 거리를 가능한 일정하게 유지하려 함
.. 따라서, 데이터량이 증가해도 검색 성능이 안정적 임
. 트리 깊이가 3~4 정도 수준으로 일정 함
. 데이터들이 항상 정렬 상태를 유지 함
- 삭제로 인한 공간 낭비 최소화
ㅇ 특징(성질)
- 하나의 노드에 여러 엔트리(값)들을 갖을 수 있음
- 노드 내부 엔트리들은 항상 정렬된 상태를 유지
- 한 노드의 자식 노드(서브 트리)의 갯수는, (자신의 엔트리 갯수) + 1 개를 갖음
. 예를들면, 루트 노드는 적어도 2개의 서브 트리를 갖음
- 자식 노드(서브 트리)들이 정렬된 상태를 유지 (좌에서 우로 순서 정렬)
- 각 노드가 최소 엔트리 개수를 나타내는 minimum 값을 지니고,
각 노드가 갖을 수 있는 최대 엔트리 개수는 minimum의 2배임
- 모든 리프 노드의 트리 깊이는 항상 같음
2. DBMS에서 B-Tree (B+ tree)
ㅇ B 트리의 수정 버전
- 트리 구조의 리프 노드(leaf node)에 만 키 값을 저장시킴
- 여기서 리프 노드는, 실제 저장된 레코드의 주소 값을 갖음
ㅇ 특징
- 특정 레코드 검색 시에,
. 정확한 인덱스 키 값, 패턴 매칭, 부분 매칭, 범위 매칭 등으로도 검색 가능
- 단, B-Tree 그 자체로는,
. 전체 일치,전방 일치 만 가능하고, 중간 일치,후방 일치는 인덱스 사용 못함
. 또한, 키 값이 변형되도(함수,연산 결과로 검색하는 경우) 인덱스 사용 못함
- 즉, B 트리는, 인덱스 컬럼의 원래 값을 변형시키지 않고 그대로 사용하는 방식
. 한편, Hash 방식 등에서는 값을 변행해서 인덱스화에 사용
. 비록, Hash 방식은 더빠른 검색이 가능하지만, 전방 일치 등이 불가능
- 순차 접근 및 임의 접근 모두 가능
. 색인순차접근방식과는 달리,
. 색인 키를 갱신하더라도 성능 저하가 발생하지 않음
- 즉, 데이터량이 증가해도 검색 성능이 안정적 임
. 트리가 항상 균형을 유지 (Balanced) 하므로
- 등호(=) 조건 뿐만 아니라, 부등호(<,>,<=,>=)를 사용한 검색 조건에서도 사용 가능
- 단, 부정형(<>,!=,NOT IN)은 사용 못함