DB에서 Index를 이용해 데이터에 접근하는 과정

※ 2021년 10월 24일에 작성된 글입니다.

📖 Index(인덱스)?

테이블에서 레코드들에 대한 검색 속도를 높이기 위해서 레코드에 대한 물리적 저장 위치를 별도로 기록한 구조

인덱스가 없으면?

모든 블록들을 순차적으로 검색해서 원하는 레코드를 찾아야 한다. O(n)

그래서 어떻게 데이터를 찾아가나?

인덱스에 이용되는 알고리즘에 따라 다르다. 아래 내용을 보자.

---

🌲 B+ Tree 인덱스

데이터베이스에서 가장 널리 사용되는 B+ 트리를 이용한 인덱스

B+ 트리 인덱스의 구성

• 실제 데이터가 저장된 레코드에 대한 주소가 기록된 단말 노드(leaf node)
• 단말 노드를 찾아가기 위한 검색키와 하위 노드의 주소로 구성된 중간 노드(internal node)
• 경로의 출발점이 되는 루트 노드(root node)

찾아가는 과정

여기서는 위 그림에서 9번에 대한 레코드를 찾는다고 가정한다.

1. 찾는 레코드(9)와 루트 노드의 검색키(5)를 비교한다.
2. 찾는 레코드(9)가 검색키 값(5) 보다 큰 값이므로 오른쪽의 포인터를 따라 하위 노드로 이동한다.
3. 중간 노드에는 두 개의 검색키(7, 8)가 있는데 찾는 레코드(9)는 이보다 더 크므로 오른쪽 포인터를 따라간다.
4. 이렇게 단말 노드에 도달하면 원하는 레코드(9)를 찾을 수 있다.

루트 노드부터 시작하여 검색키 값을 비교하여 작으면 왼쪽 포인터, 크면 오른쪽 포인터를 따라가며 단말 노드까지 도달한다.

장점

단말 노드 엔트리들이 검색키의 순서에 따라 연결되어(항상 정렬된 상태) 있어 범위(<, >) 조건 질의에도 O(log n)으로 문제가 없다.

단점

B+ 트리의 높이 만큼의 I/O 횟수가 요구되어 동등(=) 조건 질의에서 O(1)인 해시 인덱스에 비해 O(log n)으로 비효율적이다.

---

🥔 Hash 인덱스

해시 함수를 기반으로 인덱스 엔트리를 구성하는 인덱스

해시 인덱스의 구성

• 인덱스 엔트리가 저장되는 버켓(bucket)
• 각 버켓에는 해시 함수(hash function)에 해당하는 버켓 번호 부여찾아가는 과정여기서는 위 사진에서 _John Smith_에 대한 레코드를 찾는다고 가정한다.

1. 찾는 레코드의 값(John Smith)을 해시 함수에 넣는다.
2. 해시 함수의 결과로 버켓 번호(02)를 얻는다.
3. 해당 버켓(02)에서 원하는 레코드(John Smith)를 찾는다.

해시 인덱스가 설정된 필드의 값을 해시 함수에 적용하여 버켓 번호를 알아내고, 해당 버켓의 엔트리들 중에서 원하는 레코드를 찾는다.

장점

동등(=) 조건에 해당하는 레코드를 찾는 경우 O(1)로 효율적이다.

단점

인접한 범위의 값을 가진 인덱스가 동일한 버켓에 저장되는 것이 보장되지 않아(모든 값이 정렬되어 있지 않음) 범위(<, >) 조건 질의 시 문제가 있다.