[SQL] B-Tree 인덱스의 탐색 방법

B-Tree Index(균형 트리 인덱스)는 계층적 구조를 가지며, 데이터 검색 시 빠른 탐색이 가능하도록 설계된 인덱스입니다.

 

 

🔸 1. B-Tree Index 구조

B-Tree 인덱스는 다음과 같은 계층적 구조로 이루어져 있습니다.

1️⃣ Root Node (루트 노드)

• 인덱스의 최상위 노드
• 검색을 시작하는 지점

2️⃣ Branch Node (중간 노드, 분기 노드)

• 루트 노드와 리프 노드 사이에 존재
• 키 값을 기준으로 검색 방향을 결정

3️⃣ Leaf Node (리프 노드)

• 인덱스의 가장 하위 노드
• 실제 테이블의 ROWID를 저장하여 데이터 행과 연결됨
• 인접한 리프 노드끼리 연결(링크)되어 있음

 

        [Root Node]
         /       \
  [Branch 1]  [Branch 2]
     /  \         /  \
[Leaf 1] [Leaf 2] [Leaf 3] [Leaf 4]

 

 

 

---

 

🔸 2. B-Tree Index 탐색 과정

B-Tree 인덱스는 이진 탐색(Binary Search) 방식으로 데이터를 찾아가며, O(log N)의 탐색 속도를 가집니다.

✅ 탐색 과정 예제

예제: employees 테이블에서 employee_id = 103을 검색

(1) Root Node에서 탐색 시작

• employee_id 기준으로 트리를 검색
• Root Node의 키 값 확인 후, 어떤 Branch Node로 이동할지 결정

(2) Branch Node에서 탐색

• Branch Node에서 103이 어느 범위에 속하는지 확인
• 해당 키 값이 존재하는 Leaf Node로 이동

(3) Leaf Node에서 키 값을 찾음

• Leaf Node에서 103이 있는지 확인
• ROWID를 반환하여 실제 데이터가 저장된 블록을 찾아 테이블에서 데이터 조회

 

---

🔸 3. B-Tree 탐색의 주요 특징

✅ 트리의 깊이가 낮다 (일반적으로 3~4단계) → 빠른 탐색 가능
✅ 균형 트리 유지 → 데이터가 추가/삭제되어도 성능이 급격히 저하되지 않음
✅ 순차 검색 및 범위 검색에 최적화 (리프 노드끼리 연결되어 있음)
✅ WHERE 절에서 인덱스 컬럼을 활용하면 성능이 향상됨

 

 

---

🔸 4. B-Tree Index 탐색 예제 (SQL)

🔹 단일 값 검색 (Index Unique Scan)

SELECT * FROm emp WHERE emp_id = 103;

 

• "Index Unique Scan" 방식 사용
• B-Tree 탐색을 통해 빠르게 103을 찾아 해당 ROWID 반환

 

🔹 범위 검색 (Index Range Scan)

SELECT * FROM emp WHERE emp_id BETWEEN 100 AND 110;

• "Index Range Scan" 방식 사용
• Leaf Node에서 연속된 범위의 ROWID를 가져옴
• 리프 노드가 연결 리스트처럼 연결되어 있어 범위 검색이 빠름

 

🔹 최소/최대 값 검색 (Index Full Scan)

SELECT MIN(emp_id) FROM emp;

• "Index Full Scan (Min/Max)" 방식 사용
• 가장 왼쪽/오른쪽 Leaf Node로 이동하여 빠르게 값을 가져옴

 

---

🔸 5. B-Tree Index의 탐색 방식 요약

탐색 방식	설명	예제
Index Unique Scan	유니크한 값 1개 조회 (PK, UNIQUE 인덱스)	WHERE employee_id = 103
Index Range Scan	범위 검색 (연속된 키 값 검색)	WHERE employee_id BETWEEN 100 AND 110
Index Full Scan	전체 인덱스를 순차적으로 탐색	ORDER BY employee_id
Index Fast Full Scan	전체 인덱스를 병렬로 읽음 (테이블 액세스 없이)	SELECT employee_id FROM employees
Index Skip Scan	선두 컬럼을 사용하지 않고 인덱스 검색	WHERE department_id = 10 (선두 컬럼 없이 검색)

 

 

 

---

🔸 6. 결론

• B-Tree Index는 O(log N)의 탐색 속도를 제공하여, 데이터 검색이 매우 빠름
• WHERE 절에서 인덱스 컬럼을 활용하면 성능 최적화 가능
• 균형 트리 유지로 인해 데이터가 추가/삭제되어도 탐색 성능이 유지됨
• 범위 검색, 최소/최대 검색에도 효율적

🔥 "B-Tree Index를 활용하면 대량의 데이터에서도 빠른 검색이 가능!" 🚀