인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료 구조를 말한다. 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.
균형잡힌 B-Tree 기반으로 구축되어 있어서 탐색에 평균 0(logN) 시간이 걸리며 트리 생성시의 대수확장성이란 특징으로 인해 더 빠른 시간 안에 많은 양의 데이터를 빠르게 찾을 수 있기 때문.
인덱스는 보통 B-Tree라는 자료구조로 이루어져 있다. 이는 루트 노드, 리프 노드, 브랜치 노드로 이루어져 있으며 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조를 가진 균형잡힌 트리를 말한다.
예를 들어 키 57에 해당하는 데이터를 검색해야 한다고 해보자. 트리 탐색은 맨 위의 루트 노드부터 탐색이 일어나며, 브랜치 노드를 거쳐 리프 노드까지 내려온다. ‘57보다 같거나 클 때까지 ≤’ 를 기반으로 처음 루트 노드에서는 39, 83 이후 아래 노드로 내려와 46, 53, 57 등 정렬된 값을 기반으로 탐색하는 것을 볼 수 있다.
이렇게 루트 노드부터 시작하여 마지막 리프 노드에 도달해서 57이 가리키는 데이터 포인터를 통해 결과값을 반환하게 된다.
(clustered tree)
인덱스가 효율적인 이유
인덱스가 효율적인 이유는 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형 잡힌 트리 구조와 트리 깊이의 대수확장성 때문이다.
대수확장성
대수확장성이란 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미한다. 기본적으로 인덱스가 한 깊이씩 증가할 때마다 최대 인덱스 항목의 수는 4배씩 증가한다.
트리에서의 깊이
각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 말한다.
