List
1. 인덱스의 이해
1.1. 인덱스의 개념
•
DBMS에서 요청된 레코드를 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적인 구조
•
인덱스의 탐색키를 이용하여 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재
1.2. 인덱싱의 종류
•
인덱스의 종류
◦
순서 인덱스: 특정 값에 대해 정렬된 순서 구조
◦
해시 인덱스: 해싱 함수 기반의 인덱스
•
인덱스 평가 기준
◦
접근 시간
◦
유지 비용: 삽입/삭제 등의 인덱스 구조 갱신 비용
◦
공간 비용
2. 순서 인덱스
2.1. 순서 인덱스의 특징
•
탐색키로 정렬된 순차 파일에 대해 레코드에 대한 빠른 접근이 가능하도록 구성한 인덱스
•
탐색키를 정렬하여 해당 탐색키와 탐색키에 대한 레코드와의 연계를 통하여 인덱스 생성
•
종류
◦
밀집 인덱스
◦
희소 인덱스
◦
다단계 인덱스
2.2. 순차 파일
•
연속된 레코드의 접근을 빠르게 하기 위해 각각의 레코드 끝에 다음 레코드 위치를 나타내는 포인터를 가지고 있음
•
순서 인덱스
◦
순차 파일 처럼 저장된 데이터 레코드를 가지고 만든 인덱스
2.3. 인덱스 엔트리의 구조
•
구조
•
예시
2.4. 밀집 인덱스
•
모든 레코드에 대해 (탐색키 값, 포인터) 쌍을 유지
•
인덱스의 크기가 커지는 단점
2.5. 희소 인덱스
•
인덱스의 엔트리가 일부의 탐색키 값만 유지
•
순차파일 내부에서 일련의 검색을 다시해야하는 단점이 있음
2.6. 다단계 인덱스
•
4KB 크기의 블럭에 100개의 엔트리가 삽입될 때, 1억개의 레코드에 대한 순서 인덱스
◦
백만개의 블럭 → 4GB 공간 필요
•
인덱스 크기에 따른 검색 성능
◦
인덱스 크기 < 메모리 크기
▪
디스크 I/O가 줄어들어 탐색 시간 축소
◦
인덱스 크기 > 메모리 크기
▪
저장된 블럭을 여러번 나누어 읽어야함
▪
디스크 I/O 비용이 증가 → 탐색 시간 증가
→ 다단계 인덱스 구성
•
내부 인덱스와 외부 인덱스로 구성
◦
외부 인덱스
▪
내부 인덱스보다 희소한 인덱스로 구성
▪
엔트리 포인터가 내부 인덱스 블럭을 지칭
◦
포인터가 가리키는 블럭을 스캔하여 원하는 레코드보다 작거나 같은 탐색키 값 중에 가장 큰 값을 가지는 레코드 탐색
•
내부 인덱스는 백만개의 블럭을 갖는 반면, 외부 인덱스는 100개의 블럭만 사용하여 작은 크기의 외부 인덱스로 메모리 적재 가능
3. B+ 트리 인덱스
•
이진 탐색 트리
•
다단계 인덱스와 이진 탐색 트리를 결합한 트리 구조 → B+트리
3.1. B+ 트리의 구조
•
루트 노드로부터 모든 잎노드에 이르는 경로의 길이가 같은 높이 균형 트리
◦
순서 인덱스는 파일이 증가에 따라 접근 비용이 큼. 이에 대한 대안으로 제안됨
◦
상용 DBMS에서 사용되는 대표적 순서 인덱스
•
잎(단말) 노드가 연결 리스트로 연결되어 있음
•
예시)
3.2. B+ 트리의 구성 요소
•
인덱스 세트
◦
루트노드와 중간 노드로 구성
◦
단말 노드에 있는 탐색키 값을 신속히 찾아가기 위한 경로를 제공
◦
[n/2] ~ n 사이의 개수를 자식으로 소유
•
순차 세트
◦
단말 노드로 구성
◦
모든 노드가 순차적으로 서로 연결됨
◦
단말노드는 적어도 (n-1)/2개의 탐색키를 포함
◦
탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공
•
단말 노드
3.3. B+ 트리 상에서의 삽입, 삭제
•
레코드 삽입, 삭제시
◦
레코드 삽입
▪
노드에서 유지해야할 탐색키와 포인터 수 증가로 인해 노드를 분할해야하는 경우 발생
◦
레코드 삭제
▪
노드에 유지해야할 탐색키 값과 포인터 수 감소로 형제 노드와 키를 재분배 혹은 병합해야하는 경우 발생
◦
높이 균형 유지
▪
노드가 분할되거나 병합되면서 높이의 균형이 맞지않는 경우 ㅂ라생
3.4. 탐색키의 삽입
•
해당 단말 노드에 <탐색키, 포인터> 쌍으로 삽입
•
삽입시 탐색키가 순서를 유지
•
삽입 대상 노드에 추가적인 저장할 공간이 부족할 경우 분할 진행
◦
부모 노드에 탐색키를 조정하고 추가된 노드에 대한 포인터 삽입
◦
예시) COM24 삽입
3.5. 탐색키의 삭제
•
같은 탐색키 값을 가지는 다중 엔트리 존재시, 삭제될 레코드를 가리키는 엔트리 찾을때까지 탐색 후 단말 노드에서 제거
•
단말 노드에서 제거된 엔트리의 오른쪽에 있는 엔트리들은 빈공간이 없도록 왼쪽으로 이동
•
탐색키가 재분배되는 삭제
◦
단말 노드에 탐색키가 존재하지 않는 경우
◦
왼쪽의 형제 노드와 키 재분배 진행
◦
예시) COM12 삭제
