Database - 인덱스 알고리즘 정리!

인덱스 알고리즘

인덱스 알고리즘은 인덱스 페이지에 데이터를 저장하거나 찾을 때 사용되는 알고리즘을 의미한다. 대표적으로는 B-Tree 알고리즘과 Hash 알고리즘이 있다.

B-Tree 알고리즘

B-Tree는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. M개 자식을 가지는 B 트리를 M차 B-Tree라고 한다.

 

아래 그림은 차수가 3인 B-Tree 이다. 파란색 부분은 각 노드의 key를 나타낸다. B-Tree 알고리즘은 각 노드의 키보다 작은 값은 왼쪽에, 큰 값은 오른 쪽에 저장하는 방식이다. 

이는 다른 알고리즘과 비교했을 때 아래의 특징을 가진다.

• 각 노드는 항상 정렬된 상태를 가진다. 특정 값보다 크던 작던 간단하게 조회할 수 있다.
• 데이터가 중복되지 않는다.
• 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
• 데이터 조회뿐 아니라 저장, 수정, 삭제에도 항상 O(logN)의 시간복잡도를 가진다.

B+Tree 알고리즘

B-Tree 알고리즘은 모든 노드가 데이터를 포함하고 있다. 즉, 루트 노드에도 브랜치 노드에도 데이터를 포함하고 있기 때문에 트리의 모든 데이터를 얻기 위해서 모든 노드를 방문해야 한다.

 

B+Tree는 이러한 점을 개선한 자료구조이다. B+Tree는 오직 Leaf node에서만 데이터를 저장하고 나머지 노드는 포인터만 저장한다.

해당 방식은 Leaf node끼리 linked list로 연결되어 있기 때문에 전체 조회를 할때 선형 시간이 소모된다는 장점이 있다.

 

반면 BestCase의 경우 브랜치 노드에서 데이터를 찾을 수도 있지만 Leaf node까지 탐색해야 한다는 단점이 있다.

 

참고로 MySQL의 InnoDB는 B+Tree를 채택하고 있다.

B*Tree 알고리즘

B-Tree는 다른 단점도 있는데 삽입/삭제 시 구조를 유지하기 위해서 추가적인 연산이 수행되거나 새로운 노드가 생성되어야 한다는 점이다.

 

B*Tree는 노드의 추가적인 생성과 추가적인 연산의 최소화를 위해 노드를 이웃한 노드로 재배치하는 작업을 수행하게 된다. 즉, 불필요한 노드 수를 줄임으로써 데이터를 찾을 때 탐색해야 하는 노드가 적어져서 성능이 향상된다.

 

Oracle에서는 B*Tree를 채택하고 있다.

Hash 알고리즘

해시 인덱스 알고리즘을 사용하면 삽입, 탐색, 수정, 삭제 모두 O(1)을 자랑한다.

이는 탐색을 Equality(=) 연산으로 수행한다는 전제가 있다. Range Scan시에는 차차리 Full Scan이 나을 정도로 많은 연산을 수행해야 한다는 단점이 있다.

R-Tree 알고리즘

R-Tree 인덱스는 공간인덱스라고도 불리며 2차원 데이터를 인덱싱하고 검색하는 목적을 가졌다. Base 매커니즘은 B-Tree와 흡사하며, B-Tree는 1차원의 스칼라값이라면 R-Tree는 2차원 공간 개념값을 저장한다.

 

R-Tree 인덱스에서 사용하는 MySQL 데이터 타입 4가지이다.

마지막 GEOMETRY 타입은 나머지 3개 타입의 슈퍼 타입으로, 하위 세 객체를 모두 저장할 수 있다. 해당 타입들로 MBR이라는 해당 도형을 감싸는 최소 크기의 사각형을 만든다.

R-Tree 인덱스에서는 각 데이터를 우측과 같이 MBR 형태로 인덱스에 저장한다. 해당 MBR 데이터간의 포함 관계를 B-Tree 인덱스 형태로 구현한 것이 R-Tree 인덱스이다.

 

---

Reference

• https://www.programiz.com/dsa/b-tree
• https://www.geeksforgeeks.org/introduction-of-b-tree-2/
• https://velog.io/@kjh03160/DB-Index
•  https://enterone.tistory.com/228