Published 2022. 9. 6. 19:58

[Database] DBA급 개발자로 - #7 B+Tree

728x90

이전 포스팅에서 hash table에 대해 살펴봤습니다. 이번 포스팅을 통해 인덱스에 활용되는 B+Tree 자료구조에 대해 살펴보겠습니다.

B+Tree

B+Tree는 O(log n)의 시간 복잡도로 삽입, 삭제 및 검색이 가능한 자료구조입니다. 이진 탐색 트리와 다르게 하나의 부모 노드는 여러 자식 노드를 가질 수 있습니다.

B+Tree의 특징은 다음과 같습니다.
- Perfect balance : 모든 leaf node는 트리 내 동일한 깊이를 가집니다.
- 노드가 최대 M개의 자식 노드를 가질 수 있다고 가정하면, 각 노드는 최소 (M/2 -1) ~ (M-1) 개의 키를 가집니다.
- Inner node가 k 개의 키를 저장한다고 가정하면 총 k+1 자식 노드(non-null)를 가집니다.

B+Tree는 leaf node에 key와 value를 저장하고 루트와 중간 노드에는 key와 자식 노드를 가리키는 포인터(node*)를 저장합니다. B+Tree의 key는 인덱스를 구성하는 칼럼 값을 사용합니다.

B+Tree는 leaf node의 value에 어떤 값을 저장하는지에 따라 record(tuple) ID와 tuple data 저장 방식으로 분류할 수 있습니다. Record(tuple) ID는 leaf node에 튜플을 가리키는 포인터를 저장하는 방식입니다. Tuple Data 방식은 실제 튜플을 leaf node에 저장하는 방식입니다.

B+Tree Insertion

B+Tree는 데이터를 정렬된 상태로 저장합니다. 시각화 툴을 이용해 데이터가 B+Tree가 값을 어떻게 저장하는지 살펴보겠습니다.

B+Tree는 데이터가 정렬된 상태가 될 수 있도록 저장됩니다. 또한 B+Tree의 모든 leaf node가 동일한 깊이에 존재하도록 조절됩니다.

B+Tree Search

그럼 B+Tree에 저장된 데이터를 어떻게 찾는지 살펴보겠습니다. 탐색은 B+Tree의 정렬된 속성을 활용해 이진 탐색을 통해 자식 노드를 빠르게 찾을 수 있습니다.

중복 키

지금까지 B+Tree에 중복되지 않는 데이터를 어떻게 저장하고 탐색하는지 살펴봤습니다. 중복되는 키는 어떻게 처리할 수 있을까요? 대표적으로 record ID를 함께 저장하는 방식과 overflow leaf node를 사용하는 방식이 있습니다.

Record(tuple) ID

튜플의 고유한 ID를 B+Tree의 키와 함께 저장하는 방식입니다. 키가 중복되더라도 튜플 ID는 고유하기 때문에 (키, 튜플 ID)의 조합은 고유합니다.

Overflow Leaf Nodes

중복 키를 저장할 때 leaf node에 저장하는 게 아니라 overflow leaf node에 저장하는 방식입니다.

Index

Index의 종류에 따라 B+Tree에 저장되는 데이터의 형태가 달라집니다. Index는 크게 clustered index와 non-clustered index로 분류할 수 있습니다.

Clustered index란 primary key를 인덱스로 활용하며 primary key를 기준으로 테이블을 정렬합니다(Index Organized Table, IOT라고도 부릅니다). Primary key를 기준으로 테이블이 정렬됐기 때문에 primary key를 활용한 sequential scan의 성능이 좋습니다. 몇몇 DBMS는 유저가 primary key를 설정하지 않더라도 자동으로 primary key를 생성해서 테이블이 clustered index를 사용할 수 있게 합니다(MySql).
Non-clustered index는 인덱스를 구성하는 칼럼을 기준으로 정렬됩니다. Non-clustered index 형태의 B+Tree leaf node는 실제 데이터가 저장된 위치를 가리키는 포인터를 저장합니다. MySql의 경우 leaf node의 value 값으로 primary key를 저장합니다.

그럼 인덱스를 활용해서 데이터를 탐색하는 다양한 기법에 대해 살펴보겠습니다.

Clustered B+Tree 탐색

Clustered B+Tree는 range scan을 처리하는 성능이 좋습니다. 디스크 상의 데이터가 키를 기준으로 정렬됐기 때문에 순차 탐색이 가능하기 때문입니다.

Clustered index는 디스크에 키를 기준으로 정렬해서 데이터를 저장

Index Scan Page Sorting

그럼 non-clustered 인덱스의 경우 range scan 어떻게 처리할까요? Clustered 인덱스와 다르게 정렬된 키의 순서와 디스크에 저장된 데이터의 순서가 일치하지 않습니다. 따라서 데이터를 불러오기 위해 random access가 발생할 가능성이 높습니다.

Non-clustered index는 디스크의 데이터가 키를 기준으로 정렬되지 않음

Index scan page sorting은 non-clustered index를 통해 검색할 때 발생하는 random access를 줄일 수 있습니다. 먼저 찾고자 하는 데이터가 속한 page ID를 구합니다. Page ID를 모두 구하면 page ID를 기준으로 정렬시킵니다. 정렬된 순서로 페이지에 접근해서 찾고자 하는 데이터를 가져옵니다. 이 방식은 random access를 줄이고 동일한 페이지를 한 번만 접근할 수 있게 최적화합니다.

B+Tree 최적화

다음으로는 B+Tree의 저장 방식을 어떻게 최적화할 수 있는지 살펴보겠습니다.

Prefix Compression

동일한 prefix를 가진 키 값은 prefix를 한 번만 저장함으로써 최적화하는 방법입니다.

Deduplication

중복된 키를 각각 저장하는 게 아니라 한 번만 저장하고 관련된 값들만 따로 저장하는 방법입니다.

Bulk Insert

기존에 존재하는 테이블에서 새로운 B+Tree를 가장 빠르게 만드는 방법은 우선 정렬에 사용되는 키를 기준으로 테이블을 정렬 후 B+Tree를 생성하는 것입니다. 정렬된 테이블로부터 B+Tree를 만들면 leaf node -> root node의 순서로 B+Tree를 생성할 수 있어 효율적입니다. 이를 Bulk Insert라고도 합니다.

마무리

이번 포스팅을 통해서 B+Tree에 대해 살펴봤습니다. 다음 포스팅을 통해 인덱스와 관련된 동시성 문제에 대해 살펴보겠습니다.

Reference

B+Tree 시각화