[DB] 인덱스의 자료구조 B-TREE, B+TREE

 

✅ 왜 인덱스는 B-TREE, B+TREE 자료구조를 채택했을까?

인덱스 구현을 위해선 대표적으로 해시테이블과 비트리가 존재한다.

 

⏺ 해시테이블

해시테이블은 Key value를 저장하는 데이터 구조로, 빠른 데이터 검색을 할때 유용하다.

따라서 해시테이블 기반의 DB인덱스는 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현한다. 

검색 속도도 해시테이블의 Key를 찾는 속도인 O(1)이다. 

 

 

그러나 DB의 인덱스에서는 해시테이블을 사용하는 경우가 제한적이다.

 

WHY?
equal = 연산에만 특화되었기 떄문이다. 

해시함수는 값이 1개라도 달라지면 다른 해시값을 생성하기 때문에

범위 검색 (> <) 이 많이 사용되는 DB에선 해시테이블을 이용해 인덱스를 만드는게 적합하지 않다. 

 

따라서 대부분의 DB에서, 인덱스의 Defualt  자료구조를 B-TREE/ B+TREE 를 사용하게 되었다. 

 

 

 

✅ B-TREE  ?

 

(Balanced Tree)

 

 

비트리는 이진트리를 확장한 트리이다.

하나의 노드가 가질수 있는 자식노드의 개수가 여러개(최대 숫자가 2이상)인 트리 구조를 의미한다.

 

 

 

 B-TREE는 균형트리이다.

모든 리프노드가 같은 depth를 갖고 있게 설계되어 있다. 

따라서 검색에 걸리는 시간이 일정하다.

 

 

하나의 노드에 여러개의 값을 가질 수 있다.

이진트리와 다른점은 이진트리는 최대 자식이 2개이지만 b-tree는 자식의 개수가 여러개 있을 수 있다.

 

 

⏺ 시간복잡도와 B-TREE의 규칙

일반 트리는 Root 부터 탐색한다 했을 때 최악의 케이스는 편향된 트리이다. 

이때 모든 노드를 방문해야하므로, O(N)이 걸린다.

 

 

밸런스를 잘 유지하면 최악의 경우에도 O(LogN)이 보장되므로, B-TREE는 balanced tree를 사용할 수있도록 하였다.

 

 

1. node의 key의 수가 k개라면, 자식 node의 수는 k+1개이다. 

2. node의 key는 반드시 정렬된 상태여야 한다. 

3. 자식 node들의 key는 현재 node의 key를 기준으로 크기 순으로 나뉘게 된다. 

4. root node는 항상 2개 이상의 자식 node를 갖는다. (root node가 leaf node인 경우 제외) 

5. M차 트리일 때, root node와 leaf node를 제외한 모든 node는 최소 ⌈M2⌉⌈�2⌉, 최대 M�개의 서브 트리를 갖는다. 

6. 모든 leaf node들은 같은 level에 있어야 한다. 

 

 

⏺ 노드

root node : 최상단 노드

leaf node : 자식이 없는, 최하단의 노드

internal node : root와 leaf 노드를 제외한 모든 노드

 

 

 

 

 

 

 

✍️ 검색 (Search)

1. 루트노드에서 시작하여 검색하려는 값과 노드의 값의 대소비교를 한다. 

2-1. 노드의 값보다   검색값이 작으면 왼쪽 자식으로 이동

2-2. 노드의 값보다  검색값이 크면 오른쪽 자식으로 이동

3. 이를 반복하며 검색값을 가진 노드를 발견시 종료

 

 

✍️ 삽입 (Insertion)

새로운 값을 삽입할때는 다음과 같은 과정을 따른다.

 

1. 루트노드에서 시작해 삽입하려는 값과 노드의값을 비교한다.

2. 삽입하려는 값이 노드의 값보다 작으면 왼쪽자식으로 이동

3. 삽입하려는 값이 노드의 값보다 크면, 오른쪽자식으로 이동

 

이를 반복하며 삽입할 위치를 찾는데,

만약 삽입할 위치의 노드가 가득 차 있다면 노드를 분할한다.

 

** 분할 순서 규칙

 1. 가운데 값을 선택한다.

 2. 가운데 값을 기준으로
가운데 값보다 작은 것은 새 왼쪽 노드에 넣고
가운데 값보다  큰 것은 오른쪽 노드에 넣는다.

 3. 기준점이 된 값(가운데값)은 노드의 부모가 된다.
만일 이 때, 또 한번 부모 노드가 꽉차서 나누게 될 수 있는데, 그 때는 똑같이 반복한다.

만일 루트노드가 그렇게 된다면 이 노드 위에 루트를 올리면 됩니다! 즉, 새로운 루트 노드가 생성되고, 트리의 단계가 늘어난다는 얘기 입니다.

노드를 분할한 후 삽입할 위치를 찾는다.

 

 

👩‍💻 예시

 

위의 그림에서 7을 삽입한다고 가정하자. 자식은 최대 2개까지 가질 수 있다. 

 

7의 위치를 확인했을 떄 24 에서 오른쪽자식으로 내려가고,

56 위치에 도달했으나 공간이 부족하다.

따라서 가운데 값인 6을 위로 올린다.

 

그러면 또 2와 4와 6이 되면서 공간이 부족해진다. 

이경우 4을 루트로 올리고, 2는 4보다 작으므로 왼쪽으로, 6은 오른쪽으로 보낸다.

 

7은 6보다 크므로 6의 오른쪽 자식으로 삽입된다.

 

 

 

 

✍️ 삭제 (Deletion)

삭제는 공부중입니다 :) 

 

 

✅ B+TREE

 

대부분의 DATABASE에서 사용하는 인덱스의 경우 B+TREE를 따른다고 한다. B+TREE자료구조는 무엇이고 B-TREE와의 차이점은 뭘까?

 

📣 B-TREE와  차이점

B-TREE는

루트노드부터, internal node, leaf노드까지 모든 노드(key)에 값(value)이 들어있어 삽입 삭제하는데 과정이 복잡하다. 

 

이를 개선한 B+TREE는

leaf 노드에만 값(value)을 보유하게 된다. 

 

위키피디아

 

 

위의 사진보다 좀 더 쉽게 나타낸 사진이 있어서 가져왔다. 

 

 

 

출처 : Youtube 코딩애플

 

 

 root와 internal node는 분기만 준다. (Key값만 존재하고 value는 존재하지 않음)

리프노트에만 값이 존재하는데,,  리프노드끼리는 링크로 연결되어 있어서 범위 검색 (예를들면 3에서 7까지 찾기)에 아주 유용하게 사용된다고 한다!

 

 

✍️ B-TREE는 leaf node까지 안가도 탐색이 가능한 반면, B+TREE는 leaf node까지 가야만 탐색해야한다는 단점이 존재한다.

 

 

 

✅ MYSQL 실행엔진인 InnoDB의 B+TREE구조

 

일반적인 구조보다 더욱 복잡하게 되어있다.

1) 같은 레벨의 노드끼리 Double Linked List로 연결되어 있다.

2) 자식 노드는 Single Linked LIst로 연결되어있다.

 

 

---

 

https://m.blog.naver.com/eng_jisikin/220889188747https://velog.io/@sem/DB-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-B-Tree

[DB] 인덱스 자료 구조 (B-Tree)

 

https://mangkyu.tistory.com/286

[MySQL] B-Tree로 인덱스(Index)에 대해 쉽고 완벽하게 이해하기

https://youtu.be/iNvYsGKelYs