인덱싱

인덱스의 필요

1. 데이터 검색에서 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 목적

• 인덱스 : DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적인 구조
• 인덱싱 : 인덱스를 구성하고 생성하는 작업

2. 인덱스의 탐색키를 이용하여 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재

• 탐색키 : 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

인덱싱의 종류

1. 인덱스의 종류

• 순서인덱스 : 특정값에 대해 정렬된 순서 구조
• 해시인덱스 : 버킷의 범위안에서 값의 균일한 분포에 기초한 구조에 해시함수가 어떤 값이 어느 버킷에 할당되는지 결정

2. 인덱스 평가기준

• 점근시간 : 데이터를 찾는데 걸리는 시간
• 유지비용 : 새로운 데이터 삽입 및 기존 데이터 삭제연산으로 인한 인덱스 구조 갱신 비용
• 공간비용 : 인덱스 구조에 의해 사용되는 부가적인 공간비용

순서인덱스

1. 탐색키로 정렬된 순차파일에 대하여 레코드에 대한 빠른 접슨이 가능하도록 구성한 인덱스

• 탐색키를 정렬하여 해당 탐색기와 탐색기에 대한 레코드와의 연계를 통해 인덱스 생성

2. 순서인덱스 종류

• 밀집 인덱스
• 희소 인덱스
• 다단계 인덱스

밀집 인덱스

1. 모든 레코드에 대해 <탐색기값, 포인터> 쌍을 유지
   

희소인덱스

1. 인덱스의 엔트리가 일부의 탐색키 값만을 유지
   

다단계 인덱스의 필요

1. 4KB크기의 한 블럭에 100개의 엔트리가 삽입될 때, 1000,000,000 개의 레코드에 대한 순서 인덱스

• 1,000,000개의 블럭 = 4GB의 공간 필요

2. 인덱스 크키에 따른 검색 성능

• 인덱스크기 < 메모리크기 -> 디스크 I/O이 줄어 답색시간이 축소
• 인덱스크기 > 메모리크기 -> 저장된 블럭을 여러번 나누어 읽어야하기때문에 디스크 I/O 비용이 증가하여 탐색 시간이 증가
  => 다단계 인덱스 구성

다단계 인덱스

1. 내부 인덱스외 외부 인덱스로 구성

• 외부 인덱스를 내부에 인덱스보다 희소한 인덱스로 구성하여 엔트르의 포인터가 내부 인덱스 블럭을 지칭
• 포인터가 가리키는 불럭을 스캔하여 원하는 레코드보다 작거나 같은 탑색기 값중에 가장 큰 값을 가지는 레코드를 탐색

2. 내부인덱스는 1.000.000개의 블럭을 갖는 반면, 외부인덱스는 100개의 블럭만 사용하여 작은 크키의 외부 인덱스로 메모리에 적재가능
   

B+트리인덱스

• 2진탐색트리
  

1. 루트 노드로부터 모든 단말 노트에 이르는 경로의 길이가 같은 높이 규현트리

• 순서 인덱스는 파일이 커질수록 데이터 담색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
• 상용 DBMS에서도 널리 사용되는 대표적인 순서 인덱스

2. B+트리 노드 구조
   

B+트리 구성요소

1. 인덱스 세트 : 루트노드와 중간 노드로 구성

• 단말노드에 있는 탐색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적
• 2/n ~ n 사이의 개수를 자식으로 보유
  

2. 순차세트 : 단말노드로 구성

• 모든 노드가 순차적으로 서로 연결
• 단말노드는 적어도 (n-1)/2개의 탐색키를 포함
• 탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공
  

단말노드의 구성

B+ 트리의 예

B+ 트리 상에서의 삽입, 삭제

1. 레코의 삽입, 삭제시 B+트리 수정

• 레코드 삽입 : 노으에서 유지해야 할 탐색키와 포인터 수 증가로 인해 노드를 분할해야하는 경우가 발생
• 레코드 삭제 : 노드에서 유지해야할 탐색키 값과 포인터 수 감소로 형제 노드와 키를 재분부 또는 병합해야 하는 경우가 발생
• 높이 균형유지 : 노드가 분할되거나 병합되면서 높이의 균형이 맞지않는 경우가 발생

2. 삽입 : 검색과 같은 방법을 사용하여 삽입되는 레코드의 탐색키 값이 속할 단말노드를 탐색

• 해당 단말노드에 <탐색카, 포인터> 쌍을 삽입
• 삽입시 탐색키가 순서를 유지

3. 삭제 : 삭제될 레코드의 탐색키를 통해 삭제될 탐색키와 포인터를 포함한 단말 노드를 탐색

• 같은 탐색키 값을 가지는 다중 엔트리가 존재ㅔ할 경우, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 탐색 후 단말 노드에서 제거
• 단말노으에서 제거된 엔트리의 오른쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동

노드가 분할되는 삽입

-> 공간이 없으면 분할하여 삽입
1. 부모노드에 탐색키를 조정하고 추가된 노드에 대한 포인터를 삽입

탐색키가 재분배되는 삭제