[데이터베이스] B+Tree 인덱스

B+Tree 인덱스는 나무 구주로 된 인덱스로 최 정상이 Root 블록, 최 하위가 Leaf 블록, 그리고 그 사이가 Branch 블록이 들어 간다.

Root 와 Branch는 검색의 키인 사용자 ID에 대해 해당 블록이 어디에 있는지에 대한 정보를 가지고 있고 최하위층의 Leaf 블록은 실제 데이터 영역의 저장 위치의 정보를 가지고 있다.

사용자 65,535는 어디에?

루트 블록
< 50,000		브랜치1
< 98,769		브랜치2
브랜치1		브랜치2
< 600	리프1	....
---		< 65,570	리프 170
리프1		리프2
사용자 ID	보관위치	사용자ID	보관위치
1	1	...
2	73	655,535	3,276,750

또한 레코드 수가 적으면 루트가 브랜치를 켬하며, 루트와 리프밖에 없는 패턴도 존재 한다. 반대로 많은 경우 4계층 이상의 구성이 될 수도 있다.

다분기 트리와 이진 트리

브랜치 및 리프의 분기 개수가 두 개밖에 없는 것을 이진 트리라고 하고 B+Tree는 다분기 트리라고 부르며, 분기 개수가 두 개 정도가 아닌 수십 개에서 수백 개에 걸치는 경우도 있다. 분기 개수를 많이 하는 이유는 계층의 단수를 줄여서 액세스 횟수를 적게 하기 위해서다.

B-Tree는 B+Tree와는 다르게 브랜치에서도 리프뿐만 아니라 브랜치에서도 키 정보를 가지고 있다.계층구조를 작게 할 수 있다는 장점이 있지만 B+Tree 인덱스는 리프 블록에서 인접한 리프 블록으로 건나가는 것만으로 값의 탐색이 가능하기 때문에 효율적이어서 사실상 RDBMS의 표준으로 널리 사용되고 있다.