데이터베이스 인덱스는 어떻게 검색속도를 그렇게 빠르게 만드나요?

Question

대용량 데이터베이스에서 인덱스를 걸면 검색이 훨씬 빨라진다고 배우는데, 이게 어떤 자료구조 원리로 이런 속도 향상을 만들어내는지 궁금합니다.

Answer 1

안녕하세요. 이수민 전문가입니다.

인덱스가 빠른 건 전체를 안 훑어도 되게 만들어서예요. 인덱스 없는 검색은 백만 행이면 백만 행을 처음부터 끝까지 확인하는 방식이에요. 인덱스는 특정 열의 값을 미리 정렬해서 값과 위치를 짝지어 보관해둔 자료구조라, 책 뒤의 찾아보기처럼 몇 번의 이동만으로 원하는 행의 위치로 바로 가요.

핵심 자료구조는 B트리 계열이에요. 정렬된 값들을 여러 갈래로 갈라지는 트리 형태로 쌓아둔 건데, 검색할 때 루트에서 시작해 값이 있을 갈래로만 내려가요. 한 번 내려갈 때마다 후보가 수백 분의 일로 줄어서, 백만 건이든 십억 건이든 서너 번의 이동으로 도착해요. 데이터가 천 배로 늘어도 검색 횟수는 한두 번 늘어나는 정도라 대용량에서 진가가 나오는 거예요. 정렬된 상태를 유지하니 범위 검색이나 정렬 조회도 빠르고요.

공짜는 아니구 인덱스는 별도 저장 공간을 차지하고, 데이터를 넣거나 고칠 때마다 인덱스도 함께 갱신해야 해서 쓰기 작업은 오히려 느려져요. 그래서 검색에 자주 쓰는 열에만 골라 거는 게 설계 요령이에요 :)

Answer 2

안녕하세요. 강세훈 전문가입니다.

인덱스는 전체 데이터를 처음부터 끝까지 훑지 않아도 되고 세팅이 되어 있기 때문에

검색 속도가 빠르답니다. B-트리(B+트리) 구조에 값과 위치를 저장해두기 때문에 빠르답니다.

Answer 3

안녕하세요. 김재훈 전문가입니다.

데이터베이스 인덱스는 전체 데이터를 처음부터 끝까지 찾는 완탐 대신 데이터를 B-Tree 같은 정렬된 나무 구조로 조직화하여 검색 속도를 획기적으로 올립니다. B-Tree는 데이터를 정렬된 상태로 유지하면서 이진 탐색 알고리즘의 원리를 확장 적용해 트리의 루트 노드부터 자식 노드로 내려가며 매 단계마다 찾아야 할 데이터 후보군을 대폭 줄여나갑니다. 이에 따라 1억 건의 데이터 속에서도 단 몇 번의 노드 이동만으로 원하는 데이터가 위치한 실제 메모리 디스크 주소를 $O(\log N)$의 시간 복잡도로 정확히 찾아냅니다. 결국 책 맨 뒤의 색인 처럼 데이터 본문 전체를 읽지 않고 미리 잘 정리된 목차에서 위치 정보만 번개처럼 찾아내어 검색 성능을 극대화하는 원리입니다

Answer 4

안녕하세요. 박재화 전문가입니다.

데이터베이스 인덱스는 책의 찾아보기처럼 특정 값의 데이터의 어느 위치에 있는지를 벼롣의 자료구조로 정리해 둔것으로 생각하시면 됩니다.

인덱스가 없으면 원하는 데이터를 찾기 위해 테이블의 많은 행을 처음부터 확인하는 전체 탐색이 필요할 수 있는데 ,가장 흔한 인덱스 구조가 B-Tree나 B+Tree 인데, 값을 정렬된 상태로 여러 단계의 노드에 나눠 저장하는 식입니다.

검색할 때는 각 단계에서 필요한 범위만 선택해서 내려가기 때문에 수백만 건의 데이터에서도 비교 횟수를 크게 줄일 수 있는 장점이 있고, 특히 B+Tree는 값이 순서대로 연결돼 있어 특정 값 검색뿐 아니라 날짜나 가격 범위 검색에도 효율적입니다.