자료구조 in DB 인덱스

출처: https://mangkyu.tistory.com/96

RDBMS의 인덱스란?

인덱스란 DB 테이블에서 특정 데이터에 대한 검색 작업을 수행할 때, 검색 성능을 높이기 위해 사용되는 도구이다. 

만약 데이터 N개가 존재하는 테이블에서 특정 칼럼의 값이 X인 데이터를 찾기 위해서는, 전체 테이블을 모두 확인해야 하며 O(N)의 시간복잡도를 갖는다. 이를 Full table scan이라고 하는데, 하나의 데이터를 위해 매번 O(N)이 걸리는 것은 상당히 비효율적이다. 

이러한 문제를 해결하기 위한 것이 바로 인덱스이다. 주로 쓰이는 B+Tree 자료구조를 통한 인덱스를 이용 시 위와 동일한 조건에서 O(logN)의 향상된 시간복잡도를 갖는다.

 

 

인덱스에 이용되는 자료구조

1. Hash Table

해시 테이블은 Key - Value 자료구조이다.

따라서 특정 데이터의 Key를 갖고 있다면 해당 Key를 해싱하여 인덱스를 도출해내고, 이를 이용하여 해당 데이터를 찾는데 시간복잡도 O(1)이 소요된다. 

출처: https://laboputer.github.io/ps/2017/10/03/hashtable/

해시 테이블은 데이터의 검색, 삽입, 삭제에 있어 굉장히 좋은 성능을 보인다.

하지만 키 값이 중복될 시에는 검색이 어렵다는 점, 키 값의 정렬이 불가능하여 범위 탐색이 불가능하다는 점 때문에 RDBMS 인덱스에 많이 활용되지는 않는다.

 

2. B-Tree

B-Tree는 대용량 데이터를 효과적으로 관리하기 위한 자료구조이다.

기본적으로 트리 구조를 가지며 각 노드에 키 값과 그 키 값이 가리키는 데이터, 키 값의 수보다 하나 더 많은 하위 노드들을 가리키는 포인터로 구성된다. 

출처: https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC

기본적으로 Binary Tree와 비슷한 구조를 갖는데, B-Tree는 각 노드에 하나보다 많은 키를 가질 수 있다는 것이 차이점이고 이로 인해 트리의 깊이가 더 얕게 유지되며 이로 인해 더 효율적인 탐색이 가능하다.

B-Tree에서 특정 데이터를 검색하기 위해서는 O(logN)이 걸리며, 삽입, 삭제에도 O(logN)이 걸린다.

삽입과 삭제에도 O(logN)이 걸리는 이유는 Tree를 균형 상태로 만들기 위한 구조 변경이 수반되기 때문인데, 가령 특정 노드가 비대해질 경우 상위 노드에 키를 추가하고 이를 기준으로 비대 노드를 쪼개게 되며, 반대의 상황에도 일맥상통한 연산이 요구된다.

B-Tree는 Hash Table보다 검색, 삽입, 삭제 성능이 좋지는 않지만 범위 탐색이 가능한 자료구조로 더 많이 사용된다. 

 

3. B+Tree

앞서 설명한 B-Tree는 많은 이점이 존재하지만 결국에는 다음의 한계가 존재한다.

1. 특정 데이터를 찾기 위해 Full table scan을 수행하지는 않지만, 탐색 과정에서 방문한 노드의 모든 데이터에 대한 탐색이 필요함.
2. 삽입, 갱신, 삭제 등의 연산을 통해 트리 구조가 재정렬될 때 데이터의 이동도 수반되기 때문에 정렬 과정이 비효율적임.
3. 내부 노드에 데이터도 포함되기 때문에 각 노드가 포함할 수 있는 키의 개수가 적음. 따라서 트리의 깊이가 깊어지고 이는 검색 성능을 떨어뜨림.
4. Full table scan 시 시간 복잡도 O(N)을 가지기는 하지만 결국 모든 노드를 방문하여 데이터를 탐색해야 하므로 연산 성능이 떨어짐.

이러한 문제들을 해결하기 위해 B-Tree를 발전시킨 자료구조가 바로 B+Tree이다.

B+Tree는 B-Tree와 유사하지만, 내부 노드(말단 노드를 제외한 노드)에 키 값과 자식 노드에 대한 포인터만 존재하고 실질적인 데이터는 모두 말단 노드에 위치하게 되며 각 말단 노드들은 연결 리스트 형태로 이어져있다.

출처: https://www.geeksforgeeks.org/difference-between-b-tree-and-b-tree/

B+Tree는 B-Tree와 비교하여 다음의 이점을 갖는다.

1. 말단 노드에서만 실질적인 데이터의 탐색, 접근이 이루어지기 때문에 검색 연산에 있어 더 나은 성능을 가짐.
2. 말단 노드에 모든 데이터를 적재하기 때문에 데이터를 저장하기 위해 필요한 공간적인 측면에서 더 경제적임.
3. 말단 노드에 모든 데이터가 존재하기 때문에 데이터의 삽입, 갱신, 삭제 연산에 있어 덜 복잡하며 성능적 우위 존재.
4. 말단 노드들은 서로 연결되어 있고, 각 말단 노드들의 데이터는 정렬되어 있음. 따라서 범위 탐색 시 단순 선형 탐색이 가능하고 이를 통해 더 나은 성능을 보여줌.

이러한 장점들 때문에 현재 대부분의 RDBMS 인덱스는 B+Tree 자료구조로 이루어져 있다.