인덱싱

인덱스의 개념 

인덱스의 필요성

• 대량의 데이터에서 원하는 값을 빠르게 찾기 위해
• 모든 데이터를 처음부터 끝까지 순차 탐색하면 매우 비효율적
• 인덱스(index) 는 데이터를 빠르게 찾을 수 있도록 도와주는 부가적인 구조

인덱스의 정의

• 인덱스: 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 탐색키 + 포인터 구조
• 인덱싱(indexing): 인덱스를 구성하는 작업

인덱스 종류 

순서 인덱스 (Ordered Index)

• 탐색키를 정렬된 순서대로 저장하는 인덱스
• 범위 탐색에 유리하고, 이진 탐색 적용 가능

해시 인덱스 (Hashed Index)

• 탐색키를 해시 함수로 처리해 버킷 주소를 계산
• 빠른 정확한 값 탐색에 적합하지만 범위 탐색에는 부적합

인덱스 평가기준

기준	설명
접근 시간	인덱스를 통해 데이터를 찾는 데 걸리는 시간
유지 비용	삽입/삭제 시 인덱스를 재구성하는 데 드는 비용
공간 비용	인덱스를 저장하는 데 필요한 추가 공간

인덱스 크기에 따른 검색 성능 

• 인덱스 크기 > 메모리 크기: 저장된 블록을 여러번 나누어 읽어야 하기 때문에 디스크 I/O 비용증가 
• 인덱스 크기 < 메모리 크기: 디스크 I/O 줄어 탐색시간 축소 

인덱스 엔트리

구조 

탐색키값	포인터
	블록 ID	오프셋

 

• 탐색키 값: 정렬 기준이 되는 데이터 값
• 포인터: 실제 레코드가 저장된 위치를 가리킴

인덱스 구성 방식

 

밀집 인덱스 (Dense index)

• 모든 레코드에 대해 인덱스 엔트리를 유지
• 빠른 탐색 가능
• 단점: 레코드 수만큼 인덱스 크기가 커져 조회 성능 저하 

희소 인덱스(Sparse index) 

• 일부 레코드만 인덱스에 포함
• 검색 시 인덱스에서 근접한 블록까지 찾고, 그 블록 내에서 선형 탐색
• 장점: 공간 절약, 유지비용 낮음

다단계 인덱스 

• 4KB 크기의 한 블록에 100개의 엔트리가 삽입될때, 1억개의 레코드에 대한 밀집 인덱스(천개의 블록 = 4GB 공간 필요)
• 인덱스의 크기가 너무 커서 메모리에 다 못 올라올 경우 인덱스 자체를 또 인덱싱하는 방식
• 내부 인덱스 + 외부 인덱스 구조 
  • 외부 인덱스는 내부 인덱스를 가리킴 (희소)
  • 내부 인덱스는 실제 레코드를 가리킴 (보통 밀집)

B+ 트리 인덱스 

• 루트노드로부터 모든 단말노드에 이르는 경로의 길이가 같은 높이 균형 트리 
• 순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
• 상용 DBMS에서 널리 사용되는 대표적인 순서 인덱스

구성요소 

 

• 인덱스 세트 (루트 노드 + 중간 노드)
  • 단말 노드에 도달하기 위한 경로 제공
  • 각 노드는 탐색키와 포인터들을 포함
  • 자식 포인터 수: 최소 ⌈n/2⌉ ~ 최대 n
• 순차 세트 (단말 노드들)
  • 실제 레코드를 가리키는 포인터 포함
  • 인접 노드끼리 링크로 연결되어 있어 범위 탐색이 효율적
  • 탐색키 수: 최소 ⌈(n - 1)/2⌉

B+ Tree 삽입/삭제

삽입/삭제 시 중요한 특징

• 항상 균형 유지 (균형 트리)
• 삽입은 분할(split) 로 해결
• 삭제는 병합(merge) 또는 재분배(redistribute) 로 처리
• 중간 노드는 탐색만, 실제 데이터는 단말 노드에만 존재

 

•  

B+ Tree 삽입 과정

1. 단말 노드에 새로운 <탐색키, 포인터> 삽입
2. 키가 많아져 노드 용량 초과 시 → 노드 분할
3. 중간값을 부모 노드로 승격
4. 부모 노드도 넘치면 재귀적으로 분할 진행
5. 트리의 높이가 증가할 수도 있음

B+ Tree 삭제 과정

1. 삭제 대상 키를 단말 노드에서 제거
2. 제거 후 키 개수가 최소 기준보다 작으면:
   • 형제 노드와 키 재분배 시도
   • 불가능하면 병합(merge)
3. 병합 시 부모 노드에서 해당 키 제거
4. 재귀적으로 병합되며 높이 감소 가능