인덱스는 데이터를 빠르게 찾을 수 있는 하나의 장치다. 예를 들어 책의 마지막 장에 있는 찾아보기를 생각하면 된다.
인덱스는 보통 B-트리라는 자료 구조로 이루어져 있다. 이는 루트 노드, 리프 노드, 그리고 루트 노드와 리프 노드 사이에 있는 브랜치 노드로 나뉜다.
먼저 루트 노드와 리프 노드를 기반으로 설명하면 다음과 같다.
예를 들어 E를 찾는다고 하면 전체 테이블을 탐색하는 것이 아니라 E가 있을 법한 리프 노드로 들어가서 E를 탐색하면 쉽게 찾을 수 있다. 이 자료 구조 없이 E를 탐색하고자 하면 A,B,C,D 다섯 번을 탐색해야 하지만, 이렇게 노드들로 나누면 두 번만에 리프노드에서 찾을 수 있다.
좀 더 자세한 예를 들어보면, 키가 57에 해당하는 데이터를 검색해야 한다 해보자
트리 탐색은 맨 위 루트 노드부터 탐색이 일어나며 브랜치 노드를 거쳐 리프 노드까지 내려온다.
“57보다 같거나 클 때까지 ≤”를 기반으로 처음 루트 노드에서는 39, 83 이후 아래 노드로 내려와 46, 53, 57 등 정렬된 값을 기반으로 탐색하는 것을 볼 수 있다. 이렇게 루트 노드부터 시작하여 마지막 리프 노드에 도달해서 57이 가리키는 데이터 포인터를 통해 결괏값을 반환하게 된다.
인덱스가 효율적인 이유는 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형 잡힌 트리 구조와 트리 깊이의 대수확장성 때문이다.
