B트리는 이진 트리에서 발전된 모든 리프 노드들이 같은 레벨을 가지도록 유지하며 노드를 추가/삭제하는 트리이다.
추가로 정렬된 순서를 보장하고 멀티레벨 인덱싱을 통한 빠른 검색을 지원하기 때문에 DB에서 사용하는 자료구조 중 하나이다.
DB에서는 실제로 B+트리를 사용한다.
B-Tree
B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 한다.
B- Tree 의 성질
-
노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다.
-
노드에는 최대 M−1개 부터 ⌈ M/2 ⌉−1개의 키가 포함될 수 있다.
-
노드의 키가 x개라면 자식의 수는 x+1개 이다.
-
최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족한다. (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개이다.)
다음은 차수가 3인 B트리이다. 파란색 부분은 각 노드의 key를 나타내며, 빨간색 부분은 자식 노드들을 가르키는 포인터이다. key들은 노드 안에서 항상 정렬된 값을 가지며, 이진검색 트리처럼 각 key들의 왼쪽 자식들은 항상 key보다 작은 값을, 오른쪽은 큰 값을 가진다.
B+ Tree
실제 DB의 인덱싱은 B+ Tree를 사용한다고 한다.
다음 그림은 인덱싱을 나타낸 것이다. 인덱싱은 어떠한 자료를 찾는데 key값을 이용해 효과적으로 찾을 수 있는 기능이다.
다음과 같은 인덱싱을 B+트리로 나타내면 아래 그림과 같다.
B+트리에는 리프노드에 새로운 data값들이 들어가 있다.
B트리의 경우에는 편의상 data를 생략하여 그렸지만, 각 key값이 data를 가지고 있었다고 생각하자.
B+ Tree 성질
-
모든 key, data가 리프노드에 모여있다.
즉, B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data 가있다. -
모든 리프노드는 연결리스트의 형태를 띄고 있다.
B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어든다. -
리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같다.
그림의 B+트리는 리프노드의 key들을 트리가 가지고 있는 경우여서, data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어난다. 해당 경우뿐만 아니라 data의 삽입과 삭제가 일어날 때 트리의 key에 변경이 일어나지 않게 하여 더욱 편하게 B+트리를 구현하는 방법도 존재하기 때문에 작거나 같다라는 표현을 사용하였다.
노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다.
노드에는 최대 M−1개 부터 ⌈ M/2 ⌉−1개의 키가 포함될 수 있다.
노드의 키가 x개라면 자식의 수는 x+1개 이다.
최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족한다. (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개이다.)
ref : B- Tree 참고 블로그
B트리에 직접 노드 삽입하며 테스트 해보기 (BTree Visualization)
