B+트리의 동작 방식은 B트리와 굉장히 유사하지만 B+트리의 리프노드는 연결리스트의 형태를 띄어 선형 검색이 가능하다는 점에서 차이가 있다. 이러한 특징점 때문에 굉장히 작은 시간복잡도에 검색을 수행할 수 있다. 이전 B트리 포스팅에서 삽입 & 삭제 과정을 자세히 설명했기 때문에 이번 포스팅에서는 B트리와 B+트리의 차이점 위주로 설명해 보겠다.
B+ 트리
실제 DB의 인덱싱은 B+트리로 이루어져있다고 한다. 다음 그림은 인덱싱을 나타낸 것이다. 인덱싱은 어떠한 자료를 찾는데 key값을 이용해 효과적으로 찾을 수 있는 기능이다.
다음과 같은 인덱싱을 B+트리로 나타내면 아래 그림과 같다.
B+트리에는 리프노드에 새로운 data값들이 들어가 있다. B트리의 경우에는 편의상 data를 생략하여 그렸지만, 각 key값이 data를 가지고 있었다고 생각하면 되겠다. 그럼 B트리와 B+트리 달라진 점에 대해서 알아보겠다.
-
B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가진다.
-
모든 리프노드가 연결리스트의 형태를 띄고 있다. B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어든다.
-
리프노드를 순차세트, 비단말 노드를 인덱스 세트라고 한다. 즉 비 단말노드는 데이터를 저장하지 않고 오로지 인덱스 과정만 거친다. 그러므로 삽입/삭제 과정에서 필요없어질땐 삭제해줘도 된다.
-
B-Tree에서는 중복값 없이 한 개의 노드에만 key가 유일하게 존재했으나 B+Tree는 leaf 노드와 그 외 노드에 공존할 수 있다.
-
리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같습니다. 그림의 B+트리는 리프노드의 key들을 트리가 가지고 있는 경우여서, data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어난다. 해당 경우뿐만 아니라 data의 삽입과 삭제가 일어날 때 트리의 key에 변경이 일어나지 않게 하여 더욱 편하게 B+트리를 구현하는 방법도 존재하기 때문에 작거나 같다라는 표현을 사용하였다.
B+트리 특징
B트리와 같이 M차 B+트리는 다음과 같은 특징을 갖는다.
- 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다.
- 노드에는 최대 M−1개 부터 [M/2]−1개의 키가 포함될 수 있다.
- 노드의 키가 x개라면 자식의 수는 x+1개 이다.
- 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족한다. (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개이다.)
B+의 삽입, 삭제
B+ 트리의 삽입 삭제는 아래 링크를 확인하면 이해가 빠를 것이다.
B+ Tree Explained | Search, Insertion & Deletion
DB인덱싱에서 B+트리가 사용되는 이유
B+트리는 B트리와 같이 삽입/삭제/조회에 대해 O(log n)의 시간 복잡도를 갖는다. 그럼에도 불구하고 요즘은 인덱싱에서 B트리보다 B+트리가 더 많이 사용된다. 그 이유는 무엇일까.
1. 범위 검색에 유리
예를 들어 아래와 같은 범위 검색을 해야한다고 해보자.
SELECT * FROM users WHERE age BETWEEN 20 AND 30;
B트리는 트리 전체를 탐색해야 하는 반면 B+ 트리는 범위의 시작점을 찾고 리프노드에서는 순차 검색을 하면 되기 때문에 속도가 더 빠르다.
2. 순차 접근에 최적화
b+트리에서는 리프노드만 순차적으로 스캔하면되기 때문에 랜덤읽기보다 속도가 훨씬 빠르다. CPU 캐시 지역성도 뛰어나다.
3. 내부 노드의 Fan-out 증가
Fan-out이란 한 노드가 가질 수 있는 최대 자식 노드의 개수를 의미한다. B트리에서는 key와 데이터를 모두 저장하므로 저장할 수 있는 자식의 수가 상대적으로 제한되었다. 하지만 B+트리에서는 인덱싱 세트에서는 key만 저장하므로 자식을 더 많이 가질 수 있는 것이다.
Fan-out이 중요한 이유는 트리의 높이 때문이다.
데이터베이스는 대부분의 데이터를 디스크에 저장한다. 디스크는 용량이 큰 반면 속도는 느리기 때문에 디스크 접근 횟수를 최소화하는 것이 데이터베이스 성능의 핵심이다.
B 트리나 B+ 트리에서 각 노드는 하나의 디스크 블록에 저장된다. MySQL의 경우 기본적으로 한 노드가 16KB 디스크 페이지 하나를 차지한다. 이 노드들은 물리적으로 디스크의 서로 다른 위치에 흩어져 있다. 루트 노드는 디스크의 100번 섹터에, 그 자식 노드는 5000번 섹터에, 또 그 자식은 8000번 섹터에 저장되는 식이다.
이제 특정 값을 검색한다고 가정해보자. 루트 노드에서 시작해서 비교를 통해 어느 자식으로 갈지 결정하고, 그 자식 노드로 이동한다. 그런데 자식 노드는 물리적으로 다른 디스크 위치에 있으므로, 디스크에서 새로운 블록을 읽어와야 한다. 이것이 1번의 디스크 I/O인 것이다. 그 자식 노드에서 다시 비교하고 또 다음 레벨로 내려가면, 또 다시 디스크 I/O가 발생한다.
결국 루트에서 시작해서 리프 노드까지 내려가는 동안, 트리의 각 레벨마다 정확히 한 번씩 디스크 I/O가 발생한다. 트리의 높이가 4라면 루트, 레벨2, 레벨3, 리프까지 총 4번의 디스크 I/O가 필요하다. 높이가 10이면 10번, 높이가 20이면 20번이다.
이것이 Fan-out이 중요한 이유이다. Fan-out이 크면 한 노드에서 많은 자식으로 분기할 수 있어 트리의 높이가 낮아진다. 예를 들어 100만 건의 데이터를 저장할 때, 이진 트리는 높이가 약 20이 되어 20번의 디스크 I/O가 필요하지만, Fan-out이 100인 B+ 트리는 높이가 3-4 정도로 3-4번의 디스크 I/O만 필요하다. 디스크 I/O 하나가 10ms 걸린다면, 전자는 200ms, 후자는 30-40ms로 약 5-6배 차이가 난다.
B+ 트리가 B 트리보다 유리한 이유도 여기 있다. B+ 트리는 내부 노드에 데이터를 저장하지 않고 키만 저장하므로, 같은 16KB 공간에 더 많은 키를 담을 수 있다. 이는 Fan-out을 크게 늘려 트리 높이를 더욱 낮추고, 결과적으로 디스크 I/O 횟수를 줄인다. 실제로 데이터 크기가 큰 경우 B+ 트리의 Fan-out이 B 트리보다 5-10배 클 수 있고, 이는 트리 높이를 1-2 레벨 낮추어 그만큼의 디스크 I/O를 절약한다.
B+ 트리는 B 트리의 변형으로, 데이터베이스 인덱스에서 가장 널리 사용되는 자료구조이다. B 트리와의 핵심 차이점은 1. 모든 실제 데이터는 리프 노드에만 저장된다. 2. 내부 노드는 오직 인덱스(키)만 가지고 있어 탐색 경로 역할만 한다. 3. 모든 리프 노드가 연결 리스트로 연결되어 있다. 주요 장점은 리프 노드가 연결 리스트로 되어있기 때문에 범위 검색과 순차 접근에 매우 효율적이라는 점이다. 또한 내부 노드가 더 많은 키를 저장을 하고 데이터가 없어서 공간이 절약된다. B트리와 B+모두 삽입/삭제/조회에 대해 O(log n) 이라는 시간복잡도를 가지지만 위와 같은 장점때문에 요즘엔 인덱싱에 b+를 더 많이 사용한다.
