[DB] Index with B-Tree

B-Tree

• Binary Tree 에서 확장된 트리
• 한 node가 가질 수 있는 child node의 수가 2개 이상인 트리
• 각 노드는 여러개의 key를 가질 수 있고 각 key에 대응하는 data도 가지고 있다
• leaf node는 모두 같은 레벨에 존재해야 한다

---

B+ Tree

• B-Tree 에서 확장된 트리
• branch node 에는 key값만 가지고 있고, leaf node에만 data가 저장된다
• 따라서 disk I/O 시 disk block에 더 많은 key를 배치할 수 있기 때문에 key 탐색 시 B-Tree 보다 상대적으로 적은 disk block만 읽어도 된다 (리프노드를 제외하고 데이터를 담아두지 않기 때문) ⟹ 성능 개선
• leaf node는 linked list로 연결되어있다

---

B-Tree 가 선택된 이유

1) 트리 균형 유지

일반적인 트리의 경우 최악의 경우 한쪽으로 치우친 형태가 되어 시간복잡도가 O(N)이다.

Balanced Tree는 이를 개선해 트리의 균형을 유지하여 최악의 경우에도 O(logN) 시간이 걸린다.

 

2) 노드에 여러 데이터 저장됨

대량의 데이터의 경우 메모리보다는 하드디스크 혹은 SSD에 저장된다.

이러한 보조 기억장치는 block 단위로 입출력을 하기 때문에 디스크 I/O 단위로 노드의 크기를 정할 수 있는 B-Tree가 유리하다.

( 예를들어 1,024 byte block이라면, 2 byte 를 읽으나 1024 byte 읽으나 I/O 비용은 동일하다 )

---

왜 B-Tree를 사용할까?

그 이유를 다른 자료구조들과 비교하며 찾아보았다 !

O(1)인 해시테이블을 사용하지 않는 이유

해시테이블엔 등호(=) 연산에 효율적이지만,
값이 정렬되어 있지않아 부등호(<,>) 연산에는 매우 비효율적이다.

O(1)인 배열을 사용하지 않는 이유

탐색면에서는 문제가 없지만,
배열 내 데이터 저장/삭제가 매우 비효율적임

O(logN)인 다른 Balanced Tree(AVL, Red-Black Tree)를 사용하지 않는 이유

B-Tree는 하나의 노드에 여러 데이터를 저장하며, 이는 배열 자료구조로 저장되어있다.
반면 AVL, Red-Black Tree는 하나의 노드에 하나의 데이터를 저장하며 참조 포인터를 통해 메모리에 접근한다.

시간복잡도는 세 트리 모두 O(logN)이지만
B-Tree는 하나의 노드가 가질 수 있는 데이터 개수가 많으며 한 노드의 데이터를 순차적으로 접근할 수 있다는 점에서 더 효율적이다.

 

 

---

 

reference

https://helloinyong.tistory.com/296

https://steemit.com/algorithms/@soladola/b-tree

https://slenderankle.tistory.com/159