[Database] 인덱스(Index)

인덱스란?

• 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조.
  데이터 베이스에서 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.
  만약 index를 사용하지 않는다면 조회 시 전체를 탐색하는 Full Scan을 수행해야 하기에 속도가 떨어진다. 인덱스는 이를 보완해준다.

해시 테이블(Hash Table)

• 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로, 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값을 이용해 고유한 인덱스를 생성하여, 그 인덱스에 저장된 값을 꺼내오는 구조이다.

해시 테이블 기반의 DB 인덱스는 (데이터=컬럽의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다. 해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원한다.

출처

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.
위의 그림에서 처럼, 모두 다른 해시코드를 가지기 때문에, 한 번에 범위를 찾기 어렵기 때문이다.

이와 달리, 관계형 데이터베이스에서는 B-트리와 같은 자료구조를 사용하여 범위 검색이나 부등호 연산을 효율적으로 처리할 수 있다. B-트리는 데이터를 정렬된 상태로 유지하며, 범위 검색에 특화되어 있어서 부등호 연산을 사용한 쿼리를 처리하는 데 적합하다.

B+Tree

• B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다.
  범위 검색과 정렬된 순서로 데이터에 접근하는 데 효율적이며, 많은 데이터베이스 관리 시스템에서 인덱스 구조로 활용된다.

예를 들어, 학생들의 성적 데이터를 B+트리로 저장할 때, 이 B+트리에는 학생의 학번을 키(Key)로 사용하고, 각 학생의 성적을 값(Value)으로 저장할 것이다.

1. 리프 노드(데이터 노드)

• 리프 노드는 실제 데이터를 저장하는 곳이다. 이 노드들은 데이터베이스의 레코드를 포함하고 있으며, 각 레코드는 학생의 학번(키)와 성적(값)으로 구성된다.
• 예를 들어, 리프 노드 1은 학번 101부터 150까지의 학생의 성적을 저장하고, 리프 노드 2는 학번 151부터 200까지의 학생의 성적을 저장할 수 있다.
• 리프 노드들은 Linked List처럼 연결이 되어있어, 순차적으로 데이터를 읽을 때 효율적이다.

2. 인덱스 노드

• 나머지 노드들은 인덱스 역할을 한다. 데이터의 위치를 빠르게 찾기 위한 역할을 하며, 데이터 노드를 가리키는 역할을 한다.
• 인덱스 노드는 Key만 저장하고 있으며, 이 키를 사용해 데이터 노드를 검색한다.
• 예를 들어, 인덱스 노드1은 학번 100부터 200까지의 범위를 가리키고, 인덱스 노드2는 학번 201부터 300까지의 번위를 가리킨다.

3. 데이터 노드와 인덱스 노드 크기

• 데이터 노드와 인덱스 노드의 크기는 달라도 된다.
  일반적으로는 데이터 노드는 레코드(학번과 성적)를 저장하기 위한 공간이며, 인덱스 노드는 Key와 해당 키에 대한 데이터 위치 정보를 저장하기 위한 공간이다.

비록 B+Tree는 O(𝑙𝑜𝑔2𝑛) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.
데이터베이스의 크기가 커질수록 B+트리의 장점이 더욱 두드러지며, 범위 검색과 정렬이 자주 발생하는 경우에 유용한다.