[DB] Index

 

Index란?

Index는 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조입니다.

테이블 내의 1개 이상의 컬럼을 이용하여 생성할 수 있습니다. 

테이블의 특정 컬럼(Column)에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장됩니다. 컬럼의 값과 물리적 주소를 (Key, Value)의 한 쌍으로 저장합니다.

 

특정 테이블의 컬럼을 인덱싱(Indexing)하면 검색을 할 때 테이블의 레코드를 전부 다 확인하는 것이 아니라 인덱싱 되어있는 자료구조를 통해서 검색되기 때문에 검색 속도가 빨라지는 것입니다. 

 

인덱스는 책의 목차(색인)으로 비유할 수 있습니다. 책에서 원하는 내용을 찾을 때 목차 및 색인을 이용하면 훨씬 빠르게 찾을 수 있게 되는 것처럼 DB에서도 테이블에서 원하는 데이터를 찾기위해 인덱스를 이용하면 빠르게 찾을 수 있습니다.

(데이터 = 책의 내용, 인덱스 = 책의 목차, 물리적 주소 = 책의 페이지 번호)

 

동작 과정

인덱스가 생성되었다면, select 쿼리문에서 "Index 생성 컬럼을 WHERE 조건으로 걸거나", Index 컬럼을 "Order By"등의 작업을 하면 Optimizer가 판단하여 생성된 인덱스를 적용하여 SELECT문이 실행됩니다.

(Optimizer : 가장 효율적인 방법으로 SQL을 수행할 최적의 처리 경로를 생성해주는 DBMS의 핵심 엔진)

 

인덱스를 사용하지 않고 데이터를 검색하게 되면 WHERE문으로 조건에 맞는 데이터를 찾아야합니다. 테이블의 레코드를 처음부터 끝까지 모두 읽으면서 검색 조건과 맞는지를 비교해야 합니다. 이것을 "Full Table Scan"이라고 합니다. "Full Table Scan"은 가장 느린 Scanning 방법이며, 전체 데이터를 읽는 과정에서 많은 자원을 소모하게 됩니다.

 

Full Table Scan을 최소화하여 검색을 빠르게 하는 것이 Index를 사용하는 이유입니다.

 

 

인덱스 스캔에서 특정 시점까지는 Full Table Scan이 더 빠를 수 있습니다.

Index를 통한 검색은 B+Tree에서 leaf node까지 내려가서 해당 데이터를 찾기 위해 디스크로 접근하는 과정이 있습니다.

Full Table Scan을 통한 검색은 B+Tree를 거치지 않고 바로 디스크에서 데이터를 읽어옵니다.

(데이터의 양이 많지 않거나, Index가 효율적으로 설정되어 있지 않은 경우는 오히려 Table Full Scan이 더 빠릅니다.)

 

 

 

 

장점

1. 검색하는 속도와 성능 향상

인덱스에 의해 데이터들이 정렬된 형태를 갖게되어 테이블을 검색하는 속도와 성능 향상되는 장점을 가지게 됩니다.

기존에는 Where문으로 특정 조건의 데이터를 찾기 위해서 테이블의 전체를 조건과 비교해야 하는 "Full Table Scan"작업이 필요했지만, 인덱스를 이용하면 데이터들이 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있습니다.

ORDER BY, MIN/MAX 도 이미 정렬되어 있기 때문에 빠르게 수행할 수 있습니다.

 

 

단점

1. 인덱스를 관리하기 위한 추가 작업 필요
2. 추가 저장 공간 필요
3. 잘못 사용하는 경우 오히려 검색 성능 저하

Index는 검색 속도를 향상하는 장점이 있지만, 항상 정렬된 상태를 유지하기 떄문에 insert, update, delete 과정에서는 상대적으로 속도가 저하되는 단점이 있습니다. TABLE의 Index정보를 갱신하는 비용이 추가되기 때문입니다.

 

데이터의 인덱스를 제거하는 것이 아니라 '사용하지 않음'으로 처리하고 남겨두기 때문에 데이터의 수정 작업(insert, update, delete) 작업이 많은 경우 실제 데이터에 비해 인덱스가 과도하게 커지는 문제점이 발생할 수 있습니다. 별도의 메모리 공간에 저장되기 때문에 저장 공간이 많이 필요하게 됩니다.

 

 

효율적으로 사용하기

- 규모가 큰 테이블
- 수정 작업(INSERT, UPDATE, DELETE)이 자주 발생하지 않는 컬럼
- WHERE, ORDER BY, JOIN 등이 자주 사용되는 칼럼
- 데이터의 중복도가 낮은 컬럼

인덱스를 효율적으로 사용하기 위해서는 데이터의 범위가 크고, 중복이 적고, 조회가 많고, 정렬된 상태가 유용한 컬럼에서 사용하는 것이 좋습니다.

 

인덱스의 자료구조

인덱스 자료구조로 Hash Table과 B+Tree가 있습니다.

1. Hash Table

(Key, Value) 를 한 쌍으로 데이터를 저장하는 자료구조입니다. 

해시 충돌이라는 최악의 경우가 있지만, 평균적으로 O(1) 시간 복잡도를 가집니다. 매우 빠른 시간에 원하는 데이터를 탐색할 수 있는 구조입니다.

 

Hash Table을 이용한다면 인덱스는 (key, value) = (컬럼의 값, 데이터의 위치) 로 구현됩니다.

Hash Table은 등호(=)연산에 최적화되어 있기 때문에 인덱스에서는 잘 사용되지 않습니다.

데이터 베이스에서는 부등호(>,<) 연산이 자주 사용되는데, Hash Table내의 데이터들은 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 연산 할 수 없어 빠른 시간내에 찾을 수 없습니다.

 

2. B+Tree

B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장합니다.

그리고 leaf node끼리는 Linked List로 연결되어 있습니다.

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

 

<장점>

1. leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다.
   하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 Depth가 더 낮아집니다.
   트리의 Depth가 낮아지면 검색 속도를 높일 수 있습니다.
   
2. Full Table Scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고,
   leaf node끼리 Linked list로 연결되어 있기 때문에 선형 시간이 소모됩니다.
   (B-Tree는 모든 node 방문)

 

<단점>

B-Tree의 경우 검색이 하향식으로 특정 Key를 Root node에서 찾을 수 있지만,
B+Tree의 경우 반드시 특정 Key에 접근하기 위해서 leaf node까지 가야한다는 단점이 있습니다.

 

인덱스에서는 B-Tree대신 B+Tree를 주로 사용됩니다.

인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있습니다. 따라서 B+Tree의 Linked list를 이용하면 순차 검색을 효율적으로 할 수 있습니다.

B+Tree의 삽입과 삭제는 항상 leaf node에서 일어납니다.

 

더 자세한 B-Tree, B+Tree 에 대한 설명은 링크에 포스팅되어 있습니다~

[자료구조] B-Tree, B*Tree, B+Tree