[자료구조/알고리즘] 인덱스의 개념, 인덱스 자료구조 (해시 테이블, B+ Tree)

인덱스 (Index)

인덱스의 개념

인덱스(Index)란, 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조이다.

테이블의 특정 컬럼에 대해 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후, 별도의 메모리 공간에 데이터의 물리적 주소(pointer)와 함께 저장된다.

 

인덱스의 관리

인덱스가 항상 최신의 정렬 상태로 유지되어야, 원하는 값을 빠르게 탐색할 수 있다.

따라서, 인덱스가 적용된 컬럼에 대해 INSERT, DELETE, UPDATE가 수행된다면, 각각 다음과 같은 추가적 연산이 필요하다. (오버헤드 발생)

• INSERT: 새로운 데이터에 대한 인덱스를 추가
• DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행
• UPDATE: 기존의 인덱스를 사용하지 않음 처리 후, 갱신된 데이터에 대해 인덱스를 추가

인덱스의 장단점

장점

1) 테이블 조회 속도의 향상
→ 2) 성능 향상
→ 3) 전반적인 시스템의 부하 감소

 

단점

1) 인덱스 관리를 위한 별도의 저장공간 필요 (DB의 약 10%에 해당)

2) 인덱스 관리를 위한 추가 작업 필요

3) 인덱스를 잘못 사용하는 경우, 오히려 검색 성능 저하가 발생

 

인덱스의 DELETE, UPDATE 기존 인덱스를 삭제하는 것이 아니라, '사용하지 않음' 처리를 한다.

때문에, DELETE, UPDATE가 빈번하게 일어나는 속성에 인덱스를 걸게 되면, 실제 데이터보다 훨씬 많은 인덱스가 존재하게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어질 수 있다.

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

• 규모가 작지 않은 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼

 

인덱스의 자료구조

인덱스를 구현하는 자료구조는 대표적으로 해시 테이블(Hash Table)과 B+ Tree가 있다.

해시 테이블

해시 테이블은 key-value 한 쌍으로 데이터를 저장하는 자료구조로, 빠른 데이터 검색에 유용하다.

key 값을 이용하여 고유한 index를 생성하여, 해당 index에 저장된 값을 꺼내오는 구조이다.

즉, 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현한다.

 

O(1)의 시간복잡도로, 매우 빠른 검색을 지원한다.

 

하지만, 해시는 등호(=) 연산에만 특화되어 있기 때문에, 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

이러한 이유로, 데이터베이스 인덱스 자료구조로, B+ Tree가 일반적으로 사용된다.

 

B+ Tree

※ B-Tree

탐색 성능을 높이기 위해, 균형있게 높이를 유지하는 Balanced Tree의 일종이다. 자식 노드의 개수가 2개 이상이며, 노드 내의 키가 1개 이상일 수 있다.

 

B+Tree

모든 데이터를 한 번 순회하려면 트리의 모든 노드를 방문해야 하는 B-Tree의 비효율성을 개선시킨 자료구조이다.

• 오직 leaf node에만 데이터를 저장하고, leaf node가 아닌 node에는 자식 포인터만 저장한다.
• leaf node끼리는 Linked list로 연결되어 있다.
• 중간 node에서 key를 올바르게 찾아가기 위해, key가 중복될 수 있다. (leaf node에만 데이터가 저장되므로)

 

예시

인덱싱

위 인덱싱을 B+Tree로 나타낸 것

 

B+ Tree의 장점

• leaf node에만 데이터를 저장하기 때문에, 하나의 node에 더 많은 포인터를 저장할 수 있다. 따라서, 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.
• full scan 시, leaf node끼리 연결된 linked list를 통해 순차 탐색만 하면 된다. (= 부등호를 이용한 순차 검색 연산이 가능)

 

B+ Tree의 단점

• B-Tree의 경우, 특정 key를 root node에서 찾을 수 있는 최상의 경우가 존재하지만, B+ Tree는 반드시 특정 key에 접근하기 위해 leaf node까지 가야한다.

 

 

References

• https://mangkyu.tistory.com/96
• https://rebro.kr/167
• https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree