데이터베이스 인덱스는 왜 효과적일까?

인덱스

데이터를 빠르게 찾을 수 있는 하나의 장치

 

인덱스와 B-트리

인덱스는 B-트리라는 자료구조로 이루어져 있습니다. 이는 루트 노드, 리프 노드, 그리고 루트 노드와 리프 노드 사이에 있는 브랜치 노드로 나뉩니다.

 

루트 노드와 리프 노드

예를들어 A, B, C, D, E에서  E를 탐색해야 한다면 선형 탐색을 하였을 경우 5번을 탐색해야 하지만 노드들로 나누면 2번만에 리프 노드에서 찾을 수 있습니다.

 

인덱스가 효율적인 이유와 대수 확장성

인덱스가 효율적인 이유는 효율적인 트리구조와 트리 깊이의 대수확장성 때문입니다.

대수확장성이란 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미 기본적으로 인덱스가 한 깊이씩 증가할 때마다 최대 항목의 수는 4배씩 증가

트리 깊이	인덱스 항목의 수
3	64
4	256
5	1024
6	4096