B+ 트리는 데이터베이스에서 자주 사용되는 인덱싱 구조로, 데이터를 효율적으로 저장하고 검색하는데 사용한다. B+ 트리는 균형 잡힌 트리 데이터 구조로, 범위 쿼리와 검색에 특히 빠른 접근을 제공하는 것이 특징이다. Height Balance라는 특징이 있는데 어떤 Value를 검색하더라도 일정한 시간이 소요된다. 즉, 다른 말로 worst case의 performance가 안정적이어야 한다. 기본적인 구조는 Internal Node와 Leef Node가 조금 다르다 .
* Internal Node의 경우 key, Bp로 구성되어 있고 Bp가 Node의 앞 뒤를 감싸고 있다. Bp는 Block pointer를 의미한다. 그림으로 나타내면 아래와 같다.
| Bp | Key | Bp | Key | Bp |
* Leaf Node는 key,Dp,Bp로 구성되어 있고 Dp는 해당 Data page를 가리킨다.
| Key | Dp | Key | Dp | Key | Bp |
* N B+Tree를 만드는데 몇 가지 규칙들이 있다.
- Leaf node는 N/2 ~ N-1개의 Value를 갖고 있어야 한다.(혹은 [N-1/2] ~ N-1개의 Value를 갖고 있어야 한다)
- Root가 아닌 Non Leaf node 즉, 중간에 위치한 Internal node는 [N/2]~N개의 자식 노드를 갖고 있어야 한다.
- Root는 반드시 적어도 2개의 자식 노드가 있어야 한다.