테이블에서 레코드들에 대한 검색 속도를 높이기 위해서 레코드에 대한 물리적 저장 위치를 별도로 기록한 구조
모든 블록들을 순차적으로 검색해서 원하는 레코드를 찾아야 한다. O(n)
인덱스에 이용되는 알고리즘에 따라 다르다. 아래 내용을 보자.
데이터베이스에서 가장 널리 사용되는 B+ 트리를 이용한 인덱스
여기서는 위 그림에서 9번에 대한 레코드를 찾는다고 가정한다.
1. 찾는 레코드(9)와 루트 노드의 검색키(5)를 비교한다.
2. 찾는 레코드(9)가 검색키 값(5) 보다 큰 값이므로 오른쪽의 포인터를 따라 하위 노드로 이동한다.
3. 중간 노드에는 두 개의 검색키(7, 8)가 있는데 찾는 레코드(9)는 이보다 더 크므로 오른쪽 포인터를 따라간다.
4. 이렇게 단말 노드에 도달하면 원하는 레코드(9)를 찾을 수 있다.
루트 노드부터 시작하여 검색키 값을 비교하여 작으면 왼쪽 포인터, 크면 오른쪽 포인터를 따라가며 단말 노드까지 도달한다.
단말 노드 엔트리들이 검색키의 순서에 따라 연결되어(항상 정렬된 상태) 있어 범위(<, >) 조건 질의에도 O(log n)으로 문제가 없다.
B+ 트리의 높이 만큼의 I/O 횟수가 요구되어 동등(=) 조건 질의에서 O(1)인 해시 인덱스에 비해 O(log n)으로 비효율적이다.
해시 함수를 기반으로 인덱스 엔트리를 구성하는 인덱스
여기서는 위 사진에서 John Smith에 대한 레코드를 찾는다고 가정한다.
1. 찾는 레코드의 값(John Smith)을 해시 함수에 넣는다.
2. 해시 함수의 결과로 버켓 번호(02)를 얻는다.
3. 해당 버켓(02)에서 원하는 레코드(John Smith)를 찾는다.
해시 인덱스가 설정된 필드의 값을 해시 함수에 적용하여 버켓 번호를 알아내고, 해당 버켓의 엔트리들 중에서 원하는 레코드를 찾는다.
동등(=) 조건에 해당하는 레코드를 찾는 경우 O(1)로 효율적이다.
인접한 범위의 값을 가진 인덱스가 동일한 버켓에 저장되는 것이 보장되지 않아(모든 값이 정렬되어 있지 않음) 범위(<, >) 조건 질의 시 문제가 있다.