[Database] Database의 Index

Index란?

사전적 의미의 Index(색인)는 책 속의 낱말이나 구절을 등을 찾기 쉽게 일정한 순서대로 나열한 목록을 말한다.

Database에서의 Index란 데이터 검색 속도를 향상하기 위한 일종의 테이블(일종의 목록)이다.

Index를 생성하면 해당 컬럼의 데이터를 정렬하여 데이터의 위치 정보와 함께 별도의 테이블로 저장한다.

여기서 핵심은 Index는 데이터를 '정렬하여 저장한다'는 것이다.

'Friends'라는 테이블에서 'name'컬럼으로 Index를 생성한 경우.

 

Index를 사용하는 이유

조건 검색 (Where)

Database에서 테이블을 만들고 안에 데이터가 쌓이게 되면 테이블 내 레코드는 순서 없이 저장된다.

이렇게 되면 'Where'절을 통해 특정 조건을 검색할 때 저장된 레코드들을 처음부터 끝까지 다 탐색하며 조건에 맞는 레코드를 찾아야 한다.

이것을 'Full Scan'이라고 하며 모든 데이터를 하나씩 탐색하기 때문에 보통 처리 속도가 매우 느리며 O(n)의 시간 복잡도를 갖는다.

하지만 Index는 데이터들이 정렬되어 저장되어 있기 때문에 조건에 맞는 데이터들을 빠르게 탐색할 수 있다. 일반적으로 O(logN)의 시간 복잡도를 갖는다.

 

정렬 (Order by)

'Order by'는 특정 조건에 맞추어 데이터를 정렬하는 과정이며 굉장히 부하가 많은 작업이다.

정렬은 1차적으로 메모리에서 이루어지고 메모리보다 큰 작업이 필요하면 디스크 I/O가 추가적으로 발생하기 때문에 느리다.

하지만 Index는 이미 정렬되어 있기 때문에 이러한 작업이 발생하지 않는다.

 

Index 사용 시 주의할 점

Index는 SELECT를 제외한 모든 동작(INSERT, UPDATE, DELETE) 성능에 악영향을 미친다.

데이터의 수정이 일어나면 Index 테이블의 수정도 필요하기 때문에 데이터의 INSERT, UPDATE, DELETE 동작이 두 번 일어난다.

 

또한, Index는 Index 테이블을 위해 꽤나 많은 저장 공간을 필요로 한다

실제로 SQL Server의 공식 문서를 보면 기존 테이블 공간의 30~50% 정도를 Index를 위한 공간으로 잡고 있다.

 

Index에서 사용되는 자료 구조

Hash Table

Hash Table은 Key-Value로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다.

Hash Table은 Key값과 Hash Function을 이용해 고유한 index를 생성하고 그 Index에 저장된 값을 꺼내오는 구조이다.

해시 충돌이라는 변수가 존재하지만 평균적으로 O(1)의 빠른 탐색이 가능한 구조이다.

하지만 일반적으로 Index구현에는 잘 사용되지 않는데 그 이유는 Hash Table은 등호(=) 연산에 최적화되어있기 때문이다.

Database는 부등호(<, >)연산이 자주 사용되는데 Hash Table 내 데이터는 정렬되어 있지 않아 빠른 탐색이 불가하다.

B Tree

B Tree는 탐색에 최적화된 Balanced Tree의 일종이다.

Node의 자식 수 중 최대 값을 K라고 하면 해당 B Tree는 K차 B Tree라고 한다.

 

B Tree는 아래와 같은 조건을 가진다.

1. Node의 Key의 수가 K 개라면, 자식 Node의 수는 K+1개이다.
2. Node의 Key는 반드시 정렬된 상태여야 한다.
3. 자식 Node들의 Key는 현재 Node의 Key를 기준으로 크기 순으로 나뉘게 된다.
4. Root Node는 항상 2개 이상의 자식 Node를 가진다 (Root Node가 Leaf Node(자식 Node가 없는 Node)인 경우는 제외)
5. M차 트리일 때, Root Node와 Leaf Node를 제외한 모든 Node는 최소 [M/2], 최대 M개의 서브 트리를 갖는다.
6. 모든 Leaf Node들은 같은 Level에 존재한다.

3차 B Tree

주황색 부분은 자식 Node를 가리키는 포인터이고, 살구색 부분은 각 Node의 Key이다.

Node안에서 Key들은 항상 정렬된 상태를 유지하며, Binary Search Tree처럼 항상 각 Key의 왼쪽 자식은 자신보다 작고, 오른쪽 자식은 자신보다 크다.

B Tree는 최악의 경우에도 O(logN)의 탐색 시간을 보장해 준다.

 

B+ Tree

B+ Tree는 B Tree의 확장 개념으로, B Tree의 경우 Internal(Branch) Node에 Key와 Data를 저장할 수 있지만 B+ Tree의 경우 Internal Node에는 Key만 저장하고 Data는 저장하지 않는다.

오직 Leaf Node에만 Key와 Data를 저장하고, Leaf Node끼리는 Linked List로 연결한다.

모든 데이터가 Leaf Node에 있기 때문에 Full Scan시 선형 탐색만 하면 되기 때문에 B+ Tree보다 빠르다.

InnoDB 에서 사용된 B+ Tree

 

참고자료

• https://learn.microsoft.com/ko-kr/sql/relational-databases/indexes/index-disk-space-example?view=sql-server-ver16 
• 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
• https://zorba91.tistory.com/293
• https://rebro.kr/167
• https://mangkyu.tistory.com/96
• https://en.wikipedia.org/wiki/Database_index