[DB] B-Tree, B+Tree - DB Index

DB 인덱스 정리할 때, 대부분의 DBMS에서 인덱스가 B-Tree 자료구조로 저장된다고 했다. B-Tree는 어떤 자료구조이며, B+Tree와의 차이점과 왜 DB 인덱스에 사용되는지 공부해보자 ❕

 

DB 인덱스 (index)

 

 

1. B-Tree

---

B-Tree는 탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 균형 트리(Balanced Tree)의 일종이다. 이진 트리와 다르게 하나의 노드에 여러 데이터를 저장할 수 있으며, 각 key와 data가 1:1 대응하고 있다. ^모든 leaf 노드가 같은 레벨로 유지되도록 자동으로 밸런스를 맞춘다.^

 

최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 한다.

 

 

출처 : https://rebro.kr/169

 

 

특징

• 하나의 노드에 여러 key를 저장할 수 있다. (각 key는 data와 1:1 대응)
• 노드의 key들은 오름차순으로 정렬한다.
• 정렬된 순서에 따라 자녀 노드들의 key값 범위가 결정된다.
• internal 노드(leaf node, root node 제외한 노드)는 최소 하나의 key를 가지기 때문에 최소 두 개의 자식 노드를 갖는다.

 

 

조건

M차 B-Tree라면 다음 네 가지 조건을 따라야 한다.

 

• M : 각 노드의 최대 자녀 노드 수
• M-1 : 각 노드의 최대 key 수
• ⌈M/2⌉ : 각 노드의 최소 자녀 노드 수 (root node, leaf node 제외)
• ⌈M/2⌉-1 : 각 노드의 최소 key 수 (root node 제외)

 

출처 : https://rebro.kr/169

3차 B-Tree 예시이다. root 노드를 보면 하나의 노드안에 2개의 key 7, 15가 오름차순으로 정렬돼 저장되어 있고 각 키마다 data가 존재한다. 새롭게 추가되는 k가 k < 7이라면 왼쪽 자식 노드, 7 < k < 15라면 가운데 자식 노드, k > 15라면 오른쪽 자식 노드에 저장되며 부모 노드가 자식 노드들을 포인터로 가리키고 있다.

 

 

 

2. B-Tree 검색, 삽입, 삭제

---

B-Tree를 직접 만들면서 테스트해볼 수 있는 사이트

B-Tree Visualization

 

 

검색

B-Tree의 검색은 이진 트리와 비슷하다. root 노드부터 시작해 key를 탐색하고, 찾는 값이 존재한다면 검색을 멈추고, 존재하지 않는다면 해당 범위에 맞는 자식 노드로 내려가 key를 탐색한다. 이 과정을 반복해 값을 찾는다.

 

 

삽입

B-Tree의 삽입에는 조건이 있다.

1. 삽입은 항상 leaf 노드에 한다.
2. 노드가 넘치면 가운데 key를 기준으로 좌우 key들을 분할하고 가운데 key를 부모로 올린다.
   (노드가 넘친다? 위에서 본 조건으로, M차 B-Tree에서 각 노드가 가질 수 있는 최대 key 수는 M-1이므로 M-1을 초과하는 경우를 말한다)

 

 

3차 B-Tree의 데이터 삽입을 확인해보자. (^예시에서는 노드에 key만 표시하고 data를 생략했다. 실제 동작에서는 key에 대응하는 data가 있다는 것을 알고 있자!^)

✔️ 3차 B-Tree에서 최대 key수는 M-1 = 3-1 = 2이 된다.

 

 

1)

이 상태에서 30이 추가된다면, 30 > 2이므로 오른쪽 자식 노드에 삽입된다.

 

오른쪽 자식 노드 안의 key 수가 최대 개수인 2를 초과하기 때문에

조건 2번에 따라 5와 30은 분할되고 가운데 key인 15는 부모로 올라간다.

부모 노드의 포인터로 오른쪽 자식 노드를 가리키게 한다.

 

 

2)

이 상태에서 40이 추가된다면

 

오른쪽에서 두번째 노드에 40이 추가되고,

삽입된 노드 안의 key 수가 최대 개수인 2를 초과하기 때문에

조건 2번에 따라 40와 60은 분할되고 가운데 key인 50는 부모로 올라간다.

 

그럼 부모 노드에서도 key 수가 초과되어

조건 2번에 따라 30과 70은 분할되고 가운데 key인 50은 부모로 올라간다.

 

또 다시 부모 노드에서 key 수가 초과되어

조건 2번에 따라 7과 50은 분할되고 가운데 key인 15는 부모로 올라가게 된다.

 

(모든 과정에서 노드의 변경이 일어날 때마다 포인터도 변경해 줘야 한다)

 

⇒ 위에서 설명한 것처럼, 모든 leaf 노드가 같은 레벨로 유지되는 것을 볼 수 있다. 따라서 검색 시간복잡도는 avg/worst case 모두 O(logN)이 된다.

 

 

삭제

B-Tree의 삭제에는 조건이 있다.

1. 삭제는 항상 leaf 노드에 발생한다.
   (internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제하기 때문)
2. 삭제 후 최소 key 수보다 작다면 재조정한다.
   2-1. key 수가 여유있는 형제 노드의 지원을 받는다.
   2-2. 1번이 불가능하면 부모 노드의 지원을 받고 형제와 합친다.
   2-3. 2번 후 부모 노드가 최소 key 수를 만족하지 않는다면 다시 재조정한다.

(최소 key수는 B-Tree 조건에 따라 root 노드를 제외한 모든 노드에서 ⌈M/2⌉-1개여야 한다)

 

 

3차 B-Tree의 데이터 삭제를 확인해보자.

✔️ 3차 B-Tree에서 최소 key수는 ⌈1.5⌉-1 = 2-1 = 1이 된다.

 

 

1)

이 상태에서 5가 삭제된다면, 3차 B-Tree 노드의 최소 key 수인 1개보다 key 수가 작아지게 되므로 조건 2-1번에 따라 형제 노드의 지원을 받는다. (형제 노드에서 넘겨줘도 남은 형제 노드의 key 수가 1이기 때문에 2-1번으로 해결이 가능하다)

 

가운데 자식 노드는 왼쪽 자식 노드의 2를 지원받을 수 있게 된다.

만약 2를 바로 넘겨준다면 부모 노드 3보다 큰 값이 들어가게 되어버리므로, 부모 노드의 3을 지원받고 형제 노드의 2를 부모 노드에 넘긴다.

 

 

 

2)

이 상태에서 7이 삭제된다면

조건 2-1번에 따라 형제 노드의 지원을 확인한다. 근데 형제 노드 모두 key 수가 최소 key 수인 1이다.

따라서 조건 2-2번에 따라 부모 노드의 지원을 받고 형제 노드와 합쳐야 한다.

 

이때 왼쪽 형제 노드와 합친다고 하자

그럼 부모 노드의 왼쪽 key를 왼쪽 자식에게 넘겨주고, 해당 노드의 key값을 왼쪽 자식과 합친다. (지금 예시에서는 가운데 자식 노드에서 합칠 key값이 없다)

그 후 부모 노드를 한 칸 옮겨주고, 포인터도 함께 옮겨준다.

 

 

2)

이 상태에서 1이 삭제된다면

조건 2-1번에 따라 형제 노드의 지원을 확인한다.

형제 노드의 key 수가 최소 key 수 1이므로, 조건 2-2번에 따라 부모 노드의 지원을 받고 형제 노드와 합친다.

 

합쳐진 후 부모 노드에서 최소 key 수를 만족하지 않으므로 2-3번에 따라 조정해줘야 한다.

이때도 마찬가지로 2번 조건을 순차적으로 확인한다.

조건 2-1번에 따라 형제 노드의 지원을 확인한다. 형제 노드는 key를 30만을 가지고 있으므로 지원받지 못한다.

조건 2-2번에 따라 부모 노드의 지원을 받고 형제 노드와 합쳐야 한다.

 

 

 

3)

이번에는 internal 노드를 제거해보자.

조건 1번에서 ‘internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다’고 했는데, leaf 노드에 있는 데이터 중에 어떤 데이터와 위치를 바꿔줄 것인지가 중요하다.

 

⇒ 삭제할 데이터보다 작은 데이터들 중 가장 큰 데이터 or 삭제할 데이터보다 큰 데이터들 중 가장 작은 데이터와 바꿔주면 된다. 이러한 데이터는 항상 leaf 노드에 존재한다. (삭제할 key의 왼쪽 서브트리에서 가장 큰 값 or 삭제할 key의 오른쪽 서브트리에서 가장 작은 값)

 

이 예에서 15를 제거한다면

삭제할 데이터보다 작은 데이터들 중 가장 큰 데이터는 왼쪽 서브 트리 중에 가장 오른쪽 leaf node의 마지막 key가 된다.

해당 key는 12이므로 12와 15의 위치를 바꿔 삭제를 진행한다.

 

50을 제거한다면 40과 위치를 바꿔 삭제를 진행하고,

100을 제거한다면 90과 위치를 바꿔 삭제를 진행한다.

 

 

 

3. B+Tree

---

B-Tree를 개선시킨 자료구조로, 실제로 가장 많은 DBMS의 index에서 사용되는 자료구조이다. 기존 B-Tree는 특정 하나의 데이터 검색은 효율적이지만 모든 데이터를 순회할 때 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다.

오직 leaf 노드에만 data를 저장하고 leaf 노드가 아닌 노드에서는 자식 포인터만 저장한다. 따라서 부모 노드의 특정 key는 해당 key의 오른쪽 자식 서브 트리 중 가장 작은 key와 동일하다.

 

 

출처 : https://rebro.kr/167

 

 

특징

• B-Tree의 특징과 유사하다.
• 모든 노드에 데이터를 저장하는 B-Tree와 달리 오직 leaf 노드에만 데이터를 저장한다.
• 여러 노드에서 중복된 key가 존재할 수 있다. (leaf 노드에만 data를 저장하기 때문)
  
• leaf 노드들이 연결리스트(linked list)로 연결되어있다.

 

위의 그림은 3차 B+Tree 예시이다. B-Tree와 유사한 형태지만, leaf 노드에만 data를 저장하고 leaf 노드가 아닌 노드에서는 자식 포인터만 저장한다.

 

 

조건

M차 B+Tree라면 다음 네 가지 조건을 따라야 한다. (B-Tree와 동일)

• M : 각 노드의 최대 자녀 노드 수
• M-1 : 각 노드의 최대 key 수
• ⌈M/2⌉ : 각 노드의 최소 자녀 노드 수 (root node, leaf node 제외)
• ⌈M/2⌉-1 : 각 노드의 최소 key 수 (root node 제외)

 

 

 

4. B+Tree 검색, 삽입, 삭제

---

B+Tree를 직접 만들면서 테스트해볼 수 있는 사이트

B+ Tree Visualization

 

 

검색

B+Tree의 검색은 B-Tree와 동일하다. root 노드부터 시작해 key를 탐색하고, 찾는 key가 존재할 때까지 해당 범위에 맞는 자식 노드로 내려가 leaf 노드에서 key를 찾는다. key를 찾았다면 해당 key의 오른쪽 서브 트리 중 가장 작은 값 key에 대응되는 data를 읽으면 된다. (B+Tree의 데이터 검색, 삽입, 삭제는 모두 leaf 노드에서 발생한다)

 

 

삽입

B+Tree의 삽입에는 조건이 있다.

1. 삽입은 항상 leaf 노드에 한다.
2. leaf 노드가 넘치면 가운데 key를 기준으로 좌우 key들을 분할하고, 분할된 오른쪽 노드의 가장 앞에 있는 key를 부모로 올린다. (이 때, 넘치는 노드의 가운데 key는 오른쪽 노드로 들어간다)
3. leaf 노드가 아닌 노드에서 key 개수가 초과된다면, 좌우 key들을 분할하고 가운데 key를 부모로 올린다.
4. 삽입이 완료되면 leaf node끼리 연결리스트로 이어준다.

 

3차 B+Tree의 데이터 삽입을 확인해보자. (^예시에서는 노드에 key만 표시했다. 실제 동작에서는 leaf 노드에는 data가 있다는 것을 알고 있자!^)

 

 

1)

이 상태에서 28이 추가된다면

 

추가된 노드 안에 key가 최대 개수인 2를 초과하기 때문에

조건 2번에 따라 25와 28은 분할되고 오른쪽 노드의 가장 앞에 있는 key인 28은 부모로 올라간다. (이 때, leaf 노드가 넘친 것이므로 가운데 key는 오른쪽 노드에 넣고, 오른쪽 노드의 가장 작은 key가 부모 노드에 들어간다)

 

그럼 부모 노드에서도 최대 key 수를 초과하기 때문에

조건 3번에 따라 15와 28은 분할되고 가운데 key는 부모로 올라간다. (이 과정은 B-Tree와 동일하다)

 

leaf 노드에 삽입 과정이 끝나면 각 leaf 노드들을 연결리스트로 연결한다.

 

 

삭제

B-Tree의 삭제와 동일하다. 다만, 삭제할 key가 leaf 노드의 맨 앞에 위치하는 경우 부모 노드의 key도 변경해줘야 한다. (부모 노드의 key를 오른쪽 서브 트리의 가장 작은 key로 변경)

 

 

1)

이 상태에서 25가 삭제된다면

3차 B+Tree의 최소 key 수인 1보다 key 수가 작아지게 되므로 형제 노드의 지원을 받는다.

만약 28를 바로 넘겨준다면 부모 노드 28과 같은 값이 들어가게 되므로 부모 노드는 오른쪽 서브 트리의 가장 작은 값인 30으로 변경한다.

 

또, 이 상태에서 8이 삭제된다면

역시 최소 key 수인 1보다 작아지므로 형제 노드의 지원을 받는다. 왼쪽 자식노드의 가장 큰 key값을 넘겨주고 부모 노드의 key도 변경한다.

 

leaf 노드에 삭제 과정이 끝나면 각 leaf 노드들을 연결리스트로 연결한다.

 

 

 

5. DB Index에서 B+Tree

---

DB는 기본적으로 secondary storage(SSD or HDD)에 저장된다. 우리가 DB에서 해당 컬럼을 조회한다면 하드디스크에 저장된 데이터를 block 단위로 읽어 메모리(RAM)에 올린다. 우리는 이렇게 메모리에 올라온 데이터를 읽는 것이다.

secondary storage는 데이터를 처리하는 속도가 비교적 느리기 때문에, 많이 접근해 데이터를 읽어온다면 처리 속도가 느려질 것이다. 따라서 관련있는 데이터를 모아서 저장하거나 secondary storage에 최소한의 접근으로 가져온다면 빠른 처리 속도를 보장할 수 있을 것이다.

 

 

Index에서 B+Tree를 주로 사용하는 이유?

1. leaf 노드를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 확보된 메모리 공간으로 하나의 노드에 더 많은 키를 보관할 수 있게 되고, 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.
2. 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생하는데, B-Tree는 모든 노드를 트리 순회해서 확인해야 하는 반면 B+Tree는 leaf 노드끼리는 연결리스트(linked list)로 연결되어있기 때문에 순차 검색에 효율적이다. (Full Scan을 하는 경우 leaf 노드끼리 연결리스트로 연결되어 있기 때문에 선형 시간이 소모된다)

 

다만, B-Tree와 다르게 반드시 leaf 노드까지 가야만 데이터를 읽어올 수 있다는 단점이 있다.

 

 

 

 

참고자료 😃

https://rebro.kr/169

https://rebro.kr/167

https://www.youtube.com/watch?v=bqkcoSm_rCs&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=26

https://www.youtube.com/watch?v=H_u28u0usjA&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=27

https://www.youtube.com/watch?v=liPSnc6Wzfk&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=28

https://potatoggg.tistory.com/174

https://velog.io/@emplam27/자료구조-그림으로-알아보는-B-Plus-Tree