인덱스 자료구조 - 해시 테이블(Hash Table), B-Tree, B+Tree, B*Tree

인덱스는 여러 자료구조를 이용해서 구현할 수 있는데, 대표적으로 해시 테이블(Hash Table)과 B+Tree가 있다.

 

해시 테이블(Hash Table)

• key와 value를 한 쌍으로 데이터를 저장하는 자료구조
• key 값으로 value를 찾기 때문에 평균적으로 O(1)의 매우 빠른 시간으로 데이터를 탐색

But, 해시 테이블은 인덱스에서 잘 사용되지 않는다. Why?

• 해시 테이블은 등호(=) 연산에 최적화
• 데이터베이스에서는 부등호(<,>) 연산이 자주 사용되는데, 해시 테이블의 데이터는 정렬되어 있지 않으므로 기준값보다 작거나 큰 값을 빠른 시간 내에 찾을 수 없다.

 

B-Tree

• Balanced Tree의 일종으로 Binary Tree(이진 트리)를 확장하여 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2 이상인 트리 구조이다.
• B-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는 최소 M/2, 최대 M개의 서브 트리를 가짐
  6. 모든 leaf node는 같은 level에 있어야 한다.
  7. 데이터는 중복될 수 없다.

Balanced Tree를 사용하는 이유?

• 일반적인 트리인 경우 탐색하는데 평균 시간 복잡도로 O(logN)을 갖지만, 트리가 편향된 경우 최악의 시간복잡도로 O(N)을 갖는다.
• 그림의 왼쪽처럼 편향된 트리에서 root node에서 leaf node까지 탐색하면 모든 node를 방문하기 때문에 O(N)의 시간이 걸리게 된다.
• 따라서 트리가 편향되지 않도록 항상 밸런스를 유지하는 트리가 필요하다.

B-Tree의 Key 검색

1. root node부터 탐색을 시작
2. node의 key를 순회하여 k가 존재하면 탐색 종료
3. k가 존재하지 않으면 k의 값에 따라 자식 node로 내려간다.
4. leaf node까지 2~3을 반복한다.

root node의 key를 확인

7보다 크고 15보다 작으므로 사이의 포인터가 가리키는 자식으로 이동

자식으로 이동하고 나서 동일한 과정 반복

11보다 크므로 오른쪽 포인터의 자식으로 이동

마찬가지로 동일 과정 반복하여 14를 찾음

B+Tree

• B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다.
• 이를 개선시킨게 B+Tree이다.
• B+Tree는 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장
• leaf node 끼리는 linked list로 연결되어 있다.
• 또한, B+Tree에서는 leaf node에 데이터가 저장되어 중간 node에서 key가 중복될 수 있다.

B+Tree의 장점

• leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리 부분에서 효율적이다. 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도 향상
• Full scan 시 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node 끼리 linked list로 연결되어 있어 선형 시간이 소모된다.(B-Tree는 모든 node 탐색해야 함)

B+ Tree의 단점

• B-Tree의 경우 특정 key를 root node에서 찾을 수도 있지만, B+Tree는 반드시 leaf node까지 가야한다.

B-Tree 대신 B+Tree를 사용하는 이유?

• 인덱스 컬럼은 부등호를 이용한 순차 검색 연상이 자주 발생할 수 있다.
• 이때 B+Tree의 Linked List를 이용하면 순차 검색을 효율적으로 할 수 있다.

B*Tree

• B-Tree의 단점 중 하나는 Balanced Tree 구조를 유지하기 위해 추가적인 연산을 수행하거나, 새로운 노드를 생성해야 한다.
• 이를 최소화하기 위해 몇 가지 규칙이 추가된 것이 B*Tree
• 가장 큰 차이점은 B-Tree는 최소 M/2개의 키값을 가져야 했지만, B*Tree는 최소 2M/3으로 늘어남
• 노드가 가득차면 분열 대신 이웃한 형제 노드로 재배치하며, 더이상 재배치가 불가능할 때 분열
• 오라클에서 중점적으로 사용하는 인덱스 구조

 

 

 

 

 

 

 

 

 

 

 

 

 

---

참고

https://rebro.kr/169

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

https://ssocoit.tistory.com/217

[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree

https://rebro.kr/167

[DB] 11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등