DB Index

DB Index

• 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조
• 테이블의 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장

 

장점

• 테이블을 검색하는 속도와 성능이 향상됨
• 기존 방식은 특정 조건의 데이터를 찾기 위해 ‘풀 테이블 스캔(Full Table Scan)’작업이 필요
• 인덱스를 이용하면 데이터들이 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있음
• Order by, Min/Max 같은 경우도 이미 정렬이 되어 있기 때문에 빠르게 수행할 수 있음

 

단점

• 항상 정렬된 상태로 유지해야 하기 때문에 인덱스가 적용된 컬럼에 삽입(INSERT), 삭제(DELETE), 수정(UPDATE) 작업을 수행하면 다음과 같은 추가 작업이 필요

• INSERT: 새로운 데이터에 대한 인덱스 추가
• DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행 → 트리의 재구성 비용을 아낌
• UPDATE: 기존의 인덱스를 사용하지 않음 처리, 갱신된 데이터에 대한 인덱스 추가

 

위 작업이 빈번한 경우, 다음과 같은 문제

• 트리의 재정렬 비용
• 실제 데이터에 비해 인덱스가 과도하게 커지는 문제점 발생 → 추가 저장 공간 필요

 

인덱스는 테이블의 전체 데이터 중에서 10~15% 이하의 데이터를 처리하는 경우 효율적

나이나 성별과 같이 값의 range가 작은 컬럼인 경우, 인덱스를 읽고 나서 많은 데이터를 조회해야 하기 때문에 비효율적

 

인덱스를 사용하면 좋은 경우

• 규모가 큰 테이블
• 삽입, 삭제, 수정작업이 자주 발생하지 않는 컬럼
• WHERE이나 ORDER BY, JOIN 등이 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼
• Cardinality가 높은 컬럼의 경우, Index를 통해 더 많은 데이터를 필터링 할 수 있음
• SQL에서의 Cardinality는 특정 컬럼의 고유한 값의 개수를 나타내는 지표

 

인덱스의 자료구조

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

 

해시 테이블(Hash Table)

해시 테이블은 key와 value를 한 쌍으로 데이터를 저장하는 자료구조이다.

해시 테이블 기반의 DB Index는 특정 컬럼의 값과 데이터의 위치를 key와 value로 사용한다.

해시 테이블의 평균적인 시간 복잡도는 O(1)이다. 그러나 해시 충돌이 많이 발생하면 검색 성능이 하락해 시간 복잡도가 O(N)에 수렴할 수 있다.

등호 연산에는 최적화되어 있으나, 해시 테이블 내의 데이터들은 정렬되어 있지 않기 때문에 부등호 연산에는 적합하지 않다.

 

B-Tree

B-Tree는 탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 Balanced Tree의 일종이다. 자식 node의 개수가 2개 이상이며, node 내의 key가 1개 이상일 수 있다. 또한, Binary Search Tree의 특성을 포함한다고 볼 수 있다.

B-Tree는 부등호 연산에 대해 해시 테이블보다 효율적인 데이터 탐색이 가능하다. 또한 균형 트리이기에, 루트 노드에서 리프 노드까지의 거리가 모두 동일하다. 따라서 평균 시간 복잡도는 O(logN)이다. 이는 데이터 갱신이 반복되다보면 트리의 균형이 깨지면서 성능이 저하되기 때문이다.

 

B+Tree

기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한번 순회하는 데에는 트리의 모든 노드를 방문해야 한다. 이러한 단점을 개선시킨 자료구조가 B+Tree이다.

B+Tree는 오직 리프 노드에만 데이터를 저장하고 리프 노드가 아닌 노드에는 자식 포인터만 저장한다. 또한 리프 노드끼리는 연결 리스트로 구성되어 있다.

B+Tree는 반드시 리프 노드에만 데이터가 저장되기 때문에 중간 노드에서 key를 올바르게 찾아가기 위해 key가 중복될 수 있다.

리프 노드를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 노드에 더 많은 포인터를 가질 수 있으며, 이로 인해 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.

풀 스캔을 하는 경우 B+Tree는 리프 노드에만 데이터가 저장되어 있고, 리프 노드끼리 연결 리스트로 구성되어 있으므로 선형 시간이 소모된다. 반면 B-Tree는 모든 노드를 확인해야 한다.

하지만 B-Tree는 최상의 경우 특정 key를 루트 노드에서 찾을 수 있지만, B+Tree의 경우 반드시 특정 key에 접근하기 위해서 리프 노드까지 가야 하는 단점이 있다.

 

인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있으므로, B+Tree의 연결 리스트를 이용하면 이를 효율적으로 할 수 있다.

 

참고 자료

https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/

DB Index 입문

https://rebro.kr/167

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