[Index] 인덱스 종류와 자료구조

인덱스는 데이터베이스에서 데이터 검색 속도를 향상시키기 위한 자료 구조로, 특정 쿼리나 데이터베이스 작업에 맞는 인덱스 유형을 사용할 수 있다.

 

인덱스 종류

여러 종류의 인덱스가 있는데 그중 주로 사용되는 인덱스인 Unique, B-Tree, Hash, Clustered, Non-clustered 등 5가지 인덱스의 종류에 대해 알아보자..

 

유니크 인덱스 (Unique Index):

 유니크 인덱스는 해당 열의 값이 중복되지 않도록 보장하는데 사용되며, 각 값은 오직 하나의 행에만 존재할 수 있다.

• 중복된 값이 발생하지 않도록 데이터의 무결성을 유지할 수 있다. 
• 주로 기본키 (Primary Key) 제약조건을 구현하는데 사용된다.

CREATE UNIQUE INDEX idx_unique_column ON table_name (column_name);

 

 

B-Tree 인덱스:

 B-Tree 인덱스는 범위 쿼리와 정렬된 데이터에서 효과적으로 사용된다.

• 검색, 삽입, 삭제 작업이 균형 잡힌 트리 구조로 인해 빠르다.
• 대부분의 관계형 데이터베이스에서 기본적으로 사용되는 인덱스 유형이다.

CREATE INDEX idx_btree_column ON table_name (column_name);

 

 

해시 인덱스 (Hash Index):

 해시 함수를 사용하여 데이터를 해싱하고 인덱스화하는 방식으로 빠른 검색 속도를 제공한다.

• 단일 값 검색에 효과적이며, 메모리 기반 데이터베이스에서 주로 사용된다.
• 메모리 기반 데이터베이스 및 NoSQL 데이터베이스에서 사용될 수 있다.

CREATE INDEX idx_hash_column ON table_name (column_name) 
INDEXTYPE IS HASH;

 

 

클러스터 인덱스 (Clustered Index):

 데이터 행이 물리적으로 정렬되어 있고, 인덱스는 테이블 자체를 나타낸다.

• 주로 범위 쿼리에 유용하게 사용된다.

CREATE CLUSTERED INDEX idx_clustered_column ON table_name (column_name);

 

 

논 클러스터 인덱스  (Non-Clustered Index):

 데이터 행의 물리적인 순서와는 상관없이 별도로 정렬된 인덱스이다. 

• 정렬된 데이터에서 빠른 검색을 지원한다.

CREATE NONCLUSTERED INDEX idx_nonclustered_column ON table_name (column_name);

 

 

💡인덱스 결합(Composite Index)이란? 
 두 개 이상의 열에 대한 인덱스를 생성하는 것을 뜻한다. 여러 열을 묶어서 인덱스를 생성함으로써 여러 열에 기반한 검색 및 정렬이 가능해진다.
즉, 여러 열에 대한 검색이나 정렬을 할 경우 성능을 향상시킬 수 있으며 여러 열을 조합한 유니크한 값을 생성하는데 유용하다. 

 

 

---

 

 

 

인덱스의 대표적인 자료구조 Hash Table & B+Tree

 

해시 테이블 (Hash Table)

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

• key, value로 쌍을 표현하며, key값을 이용해 대응되는 value값을 구하는 방식이다.
• 해시 충돌이라는 변수가 존재하지만 평균적으로 **O(1)**의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 구조이다.

• 해시 테이블을 이용한다면 인덱스는 **(key, value) = (컬럼의 값, 데이터의 위치)**로 구현하는데, 해시 테이블은 실제로 인덱스에서 잘 사용되지 않는다.
• 그 이유는, 해시 테이블은 등호(=) 연산에 최적화되어있으며, 해시 테이블 내의 데이터들은 정렬되어 있지 않기 때문이다.

 

B+Tree

• B-Tree

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

 

• B+Tree

B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다. leaf node끼리는 Linked list로 연결되어있다.

 

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

2. Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다.

 

삽입

1. key의 수가 최대보다 적은 leaf node에 삽입하는 경우

해당 node의 가장 앞이 아닌 곳에 삽입되는 경우는 단순히 삽입해 주면 된다.

하지만, leaf node의 가장 앞에 삽입되는 경우는, 해당 node를 가리키는 부모 node의 포인터의 오른쪽에 위치한 key를 K로 바꿔준다. 그리고 leaf node끼리 Linked list로 이어줘야 하므로 삽입된 key에 Linked list로 연결한다.

1. key의 수가 최대인 leaf node에 삽입하는 경우

key의 수가 최대이므로 삽입하는 경우 분할을 해주어야 한다. 만약 중간 node에서 분할이 일어나는 경우는 B-Tree와 동일하게 해주면 된다.

leaf node에서 분할이 일어나는 경우는 중간 key를 부모 node로 올려주는데 이때, 오른쪽 node에 중간 key를 붙여 분할한다. 그리고 분할된 두 node를 Linked List로 연결해준다.

 

삭제

1. 삭제할 key가 leaf node의 가장 앞에 있지 않은 경우

B-Tree와 동일한 방법으로 삭제된다.

1. 삭제할 key가 leaf node의 가장 앞에 위치한 경우

이 경우는 leaf node가 아닌 node에 key가 중복해서 존재한다. 따라서 해당 key를 노드보다 오른쪽에 있으면서 가장 작은 값으로 바꿔주어야 한다.