B-트리 와 B+-트리

 

1. B-트리

- 트리의 각 노드가 적어도 반 이상 채워져 있어야 한다.

- 트리의 높이가 균형을 이루어야 한다.

- 키 값의 삽입 삭제 시에는 자동으로 합병이나 분할한다.

- 루트, 리프 제외한 모든 노드 : 최소 m/2에서 m개의 서브 트리를 갖는다.

- 루트는 리프가 아닌 이상 적어도 두 개의 서브 트리를 갖는다.

- 리프가 아닌 노드의 키 값의 수는 그 노드의 서브 트리의 수보다 하나 적다.

- 한 노드 안에 있는 키 값은 오름차순으로 정렬되어 있다.

- 임의의 킷값 k의 왼편 부트리의 모든 킷값은 k보다 작고 오른편 부트리의 킷값은 k보다 크다.

2. B⁺-트리

- B-트리의 변형으로 인덱스는 B-트리와 같은 인덱스 부분과 파일속 모든 레코드의 키 값으로 구성된 엔트리의 순차집합으로 나누어 짐

- 순차집합이 키 값의 순서대로 연결리스트를 형성하고 있어 순차적으로 접근 가능

- 특정 레코드 삭제시 순차집합의 해당 레코드의 키를 제거함으로써 인덱스 부분은 변경할 필요가 없다.