[DB] 이진 탐색 트리부터 B+Tree까지 그리고 인덱스 - 1

인덱스의 특징을 이해하는 데에 있어서 인덱스의 데이터 저장 방식인 B+Tree를 아는 것이 좋다고 생각돼서 전체적인 목차를 이진 탐색 트리, B-Tree, 인덱스, B+Tree의 순으로 작성하려 한다.

 

 

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리는 이진 탐색(Binary Search)의 효율적인 탐색과 빈번한 자료 삽입과 삭제에 용이한 연결 리스트(Linked List)의 장점을 결합한 정렬된 이진트리이다.

 

- 이진 트리

이진 트리란 모든 노드의 최대 차수가 2개인 트리를 말한다.

이미지 출처: https://galid1.tistory.com/176

 

 

이진 탐색?? 연결리스트??

- 이진 탐색

이진 탐색은 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘으로 다음과 같은 순서를 거친다.

1. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교
2. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로 하고, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색
>> 해당 값을 찾을 때까지 1번과 2번의 과정을 반복

이렇게 처음에 N개의 크기인 배열에서 하나의 과정이 지나감에 따라 탐색할 배열의 크기가 반씩 줄어들기 때문에 N, N/2, N/4, ..., 1로 실행된다. 따라서 이진 탐색의 시간 복잡도는 O(log N)이다.

 

 

- 연결 리스트 (Linked List)

연결 리스트는 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식의 자료구조이다.

단일 연결 리스트(Singly Linked List)의 경우 각 노드들은 데이터와 다음 노드를 가리키는 포인터를 가지고 연결되어 있다.

이미지 출처: https://www.alphacodingskills.com/ds/notes/linked-list.php

 

그렇기 때문에 삽입과 삭제 시에 가리키는 노드만 변경해주면 되기 때문에 연결 리스트는 삽입과 삭제시에 용이하다는 특징을 가지고 있다.

이미지 출처: https://qnaplus.com/insert-element-singly-linked-list/

 

하지만 위와 같이 맨 앞 또는 맨 뒤의 데이터에 대해서만 시간 복잡도가 O(1)이 소요된다.

 

실제로는 특정 노드 다음에 삽입과 삭제가 이루어지는 경우가 종종 발생하게 되는데, 이런 경우에는 원하는 노드에 탐색(접근)을 한 다음 삽입 또는 삭제가 발생한다.

이미지 출처: https://qnaplus.com/insert-element-singly-linked-list/

이런 경우에는 시간 복잡도가 탐색하는 O(n)과 삽입 또는 삭제하는 O(1)이 더해진 O(n+1)만큼의 시간이 소요되게 된다.

 

 

따라서 삽입과 삭제를 하는데에 용이한 연결리스트의 특징과 탐색의 비용이 효율적인 이진 탐색의 특징을 가지고 만들어진 자료구조가 바로 이진 탐색 트리이다.

 

 

 

구구절절 여러 이야기를 적었지만 결국 이진 탐색 트리는 연결 리스트의 장점과 이진 탐색의 장점의 조건이 추가된 이진 트리이다. 여기서 말한 조건이란 다음을 의미한다.

조건 1. 루트 노드의 왼쪽 자식 노드는 루트 노드보다 크기가 작다.
조건 2. 루트 노드의 오른쪽 자식 노드는 루트 노드보다 크기가 크다.

이미지 출처: https://imgur.com/nCYjtI7

 

 

이진 탐색 트리가 모든 것을 해결한 '것' 같았지만 최악의 경우(worst case)인 편향 트리(degenerated tree)의 모습인 경우라면 탐색의 시간 복잡도가 O(n)이 되게 되면서 이진 탐색의 장점을 가졌다고 보기 어렵다.

이미지 출처: http://stoimen.com/2012/07/03/computer-algorithms-balancing-a-binary-search-tree/

 

• 균형 잡힌 이진 탐색 트리(BST)의 경우 시간 복잡도가 O(log N)
• 균형 잡히지 않은 이진 탐색 트리의 경우 시간 복잡도가 O(N)

 

이러한 BST가 가지는 문제를 해결하기 위해 나온 자료구조 중 B-Tree에 대해 알아보려 한다.

 

 

B-Tree

- B-Tree는 이진 탐색 트리가 최악인 경우(편향 트리일 때)에 가지는 문제를 해결하기 위해 나온 self-balacing tree이다.

- 다시 말해 효율적인 검색, 삽입, 삭제 작업이 이루어지는 균형 잡힌 트리이다.

궁금해!! - 1
Q. 지금까지 이진 트리, 이진 탐색 트리에 대해 얘기했으면서 B-Tree는 왜 이진트리라고 정의하지 않았나??
A. 이진 트리는 각 노드가 최대 2개의 자식을 가질 수 있는 반면, B-Tree는 2개 이상의 자식을 가질 수 있기 때문

 

B-Tree는 다음과 같은 형태를 띄고 있다.

이미지 출처: https://rebro.kr/169

 

모든 특징들을 다 기억할 순 없겠지만 B-Tree의 특징을 나열해 보면 다음과 같다.

특징 1. 하나의 노드에는 2개 이상의 키가 존재할 수 있으며 항상 정렬된 상태로 저장된다.
특징 2. 특정 노드의 차수(자식 노드의 수)가 2개 이상일 수 있고, 최대 자식 노드의 수가 M개인 B-Tree를 M차 B-Tree라고 한다.
특징 3. M차 B-Tree는 하나의 노드에 가질 수 있는 최대 키의 개수는 M-1개이다. (만약 하나의 노드가 최대 키의 개수를 초과하면 분할 과정을 거친다.)
특징 4. M차 B-Tree에서 특정 노드가 가질 수 있는 자식 노드의 개수는 floor(M/2)개 부터 M개다.
특징 5. 특정 노드의 키의 개수가 K개라면 자식 노드의 수는 K+1개이다.
특징 6. 노드의 키는 반드시 정렬된 상태여야 하고, 특정 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 값들이, 오른쪽 서브 트리에는 큰 값들로 구성되어야 한다.
특징 7. 루트 노드는 항상 2개 이상의 자식 노드를 가져야 한다. (단, 루트 노드가 리프 노드인 경우는 제외)
특징 8. 최상위 노드를 루트 노드, 최하위 노드를 리프 노드, 그 사이 노드들을 브랜치 노드라고 부른다.
특징 9. 모든 리프 노드(leaf node)들은 같은 레벨(level)에 존재해야 한다.
특징 10. INSERT, DELETE와 같은 작업이 일어나도 항상 균형을 유지한다.

이미지 출처: https://zorba91.tistory.com/293

 

궁금해!! - 2
Q. B-Tree에서 중복된 키 값을 허용하지 않는다....라는 글을 많이 봤는데 만약 중복값이 들어가게 된다면??
A. 중복 데이터가 B-Tree에 삽입될 때 알고리즘의 구현에 따라 달라진다.

1. 중복되지 않은 키를 삽입할 때와 마찬가지로 삽입되어야 할 노드까지 탐색을 수행한다.
2. 동일한 값을 가지는 키가 포함되어 있다면 구현에 따라서 1) 기존 키를 새 키(삽입한 중복 키)로 덮어쓰거나 별도의 노드에 새 키를 삽입한다.

 

여러 특징들이 존재하지만 결국 B-Tree에서 중요한 건 열 번째 특징인 self-balancing이 가장 중요한 것이라 생각된다.

 

그래서 이 포스팅에서는 데이터를 삽입할 때 분할이 이루어지는 경우에 대해서만 다루려고 한다.

(만약 좀 더 시각적으로 보고 직접 해보고 싶으신 분이라면 아래 링크에서 원하는 자료구조를 선택해서 진행하면 될 것 같습니다.)

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Data Structure Visualization

 

B-Tree의 삽입 과정 (분할)

아래 링크를 참고하여 작성한 예시입니다.

https://rebro.kr/169

[DB] 10. B-Tree (B-트리)

 

 

B-Tree에서도 데이터를 삽입하기 전에 선행적으로 데이터의 탐색이 이루어져야 하는데, B-Tree의 탐색은 루트 노드에서 시작하여 하향식으로 탐색하는 이진 탐색 트리의 탐색과 비슷하다.

(B-Tree의 탐색 과정은 생략할 것이기 때문에 과정만 나열해 보겠습니다)

1. 루트 노드부터 탐색을 시작한다.
2-1. 노드를 순회하며 찾으려는 값(K)이 존재하면 탐색을 종료한다.
2-2. 찾으려는 값이 존재하지 않는다면 포인터를 통해 자식 노드로 내려간다.
리프 노드(leaf node)까지 2-1, 2-2번의 과정을 반복한다.

 

B-Tree의 데이터 삽입 과정은 다음과 같습니다.

0. 빈 트리인 경우 루트 노드를 만들어 K를 추가한다.
루트 노드가 가득 찬 경우 노드를 분리하여 리프 노드를 생성한다.

1. K가 들어갈 leaf node를 검색 과정과 동일하게 탐색한다.
2-1. 해당 leaf node에 자리가 남아있다면 정렬을 유지하도록 위치시킨다.
2-2. 해당 leaf node가 꽉 차 있다면 K를 삽입한 후 해당 node를 분할한다.

 

B-Tree에 데이터를 삽입하기 전 초기 상태는 다음과 같습니다.

 

1. (탐색 과정 생략) 삽입할 13이라는 값이 들어갈 노드를 탐색

13은 12와 14의 사잇값

2. 값이 들어갈 노드에 삽입할 키를 추가했으나 한 노드가 가질 수 있는 최대 범위를 벗어났기 때문에 해당 노드를 분할해야 한다.

B-Tree의 특징에서 얘기한 특징 3번을 다시 가져와보겠다.
--
특징 3. M차 B-Tree는 하나의 노드에 가질 수 있는 최대 키의 개수는 M-1개이다. (만약 하나의 노드가 최대 키의 개수를 초과하면 분할 과정을 거친다.)
--
즉 예시로 사용되는 B-Tree는 3차 B 트리이기 때문에 한 노드당 들어갈 수 있는 최대 키의 개수는 2개이다.

 

하나의 노드에 들어갈 수 있는 최대 키의 개수는 초과한 상태

 

3. 해당 노드의 중간 값인 13이 부모 노드와 합쳐지게 되고 부모 노드가 가지는 키(9, 11) 중에서 11보다 큰 값이기 때문에 오른쪽에 위치하게 된다. 자식 노드들도 키 값에 따라 각각 분할하게 된다.

최대 키의 개수가 초과된 노드의 중간 값인 13이 분할

부모 노드가 가지는 키의 값과 비교했을 때 분할된 값(13)이 11보다 크기 때문에 11의 우측에 위치             또한, 12와 14는 각각 13의 왼쪽과 오른쪽의 자식이 된다.

 

4. 분할이 끝난 이후에도 합쳐진 노드에서 최대 키의 개수를 초과했으므로 분할을 다시 수행한다.

3번 과정과 동일

3번 과정과 동일

 

5. 루트 노드 또한 최대 키의 개수를 초과했기 때문에 또다시 분할 과정을 수행한다.

3번 과정과 동일

 

6. 더 이상 분할을 할 노드가 존재하지 않으므로 다음과 같은 형태가 되게 된다.

분할 과정을 전부 마친 상태

 

삭제를 해야 하는 경우가 더 복잡하고 따져야 할 경우의 수도 많지만 설명하고자 하는 건 B-Tree는 self-balancing을 하며 균형을 이루는 트리라는 것이기 때문에 생략하겠다.

 

 

---

 

이번 [DB] 이진 탐색 트리부터 B+Tree까지 그리고 인덱스 - 1에서는 이진 탐색 트리와 B-Tree까지 알아보았다.

 

다음번엔 [DB] 이진 탐색 트리부터 B+Tree까지 그리고 인덱스 - 2에서 B-Tree를 개선한 자료구조인 B+Tree와 인덱스를 알아보려 한다.

 

 

참고

• 링크
• 링크
• 링크
• 링크

• 링크
• 링크
• 링크
• 링크