[HUFS/데이터베이스] #15 인덱스

B-트리

화일의 기본적인 조직 방법

데이터가 입력되는 순서대로 쌓이는 순차 방법은 레코드들의 논리적 순서가 저장 순서와 동일

~ 물리적 순서대로 레코드에 접근하며 파일 복사, 순차적 일괄 처리에 응용

 

엔트리 순차 화일과 키 순차 화일

순차적으로 쌓이는 데이터들을 인덱스 화일의 키 값으로 정리

키가 복합적으로 적용되는 다중키 파일 -> 인덱스의 키 값으로 레코드를 빠르게 탐색

인덱스의 종류)

• 기본키에 대한 인덱스라면 기본 인덱스, 아니라면 보조 인데스
• 레코드가 키 값 순으로 정렬되었다면 집중 인덱스, 아니라면 비집중 인데스
• 모든 키에 대해서 인덱스 엔트리가 있다면 밀집 인덱스, 아니라면 희소 인데스

* 인덱스 엔트리: 레코드 키 값 + 포인터

 

디스크에 인덱스를 만들 때, 데이터를 저장하는 탐색 트리

 

2- 원 탐색 트리 / 3-원 탐색 트리

m- 원 탐색 트리

m-원 탐색 트리 중 모든 자식 노드가 균형을 유지하는 경우 B-트리라고 한다

 

하나의 노드가 하나의 디스크 페이지에 저장된다

B-트리의 조건)

1. 공백이거나 높이가 1이상인 m-원 탐색 트리
2. 루트와 리프를 제외한 내부 노트는 최소 m/2, 최대 m개의 서브트리를 가짐
3. 루트는 그 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 가짐
4. 모든 리프는 같은 레벨에 있음

B-트리는 검색/삽입/삭제/변경 연산을 할 때, 중위 순회하며 키 순서로 탐색하고

어떤 연산을 수행하더라도 결과적으로 균형을 유지해야 한다

 

삽입 연산의 경우 ~ 노드가 오버플로우되면 노드가 분할하며 트리가 깊어진다 (ppt 참고)

삭제 연산의 경우 ~ 노드가 언더플로우되면 노드가 병합하며 트리가 얕아진다 (ppt 참고)

B-트리는 순차접근시 과도한 디스크I/O가 발생하기 때문에

인덱스 세트와 순차 세트로 구성된 B+트리가 등장

 

인덱스 세트는 키에 대한 경로만 제공 / 리프 노드로 구성된 순차 세트는 경로에 따라 순차적 연결

B+트리의 레코드 삭제

해시 인덱스

해싱(hashing): 다른 레코드의 참조 없이 계산에 의해 목표 레코드의 접근을 직접 하는 것

~ 키 값과 레코드 주소 사이의 사상 관계를 해싱 함수로 설정한다 (키 -> 주소) 삽입/검색

 

버킷 해싱은 데이터를 버킷에 저장하는 방식이다

 

해싱 함수의 키 값이 버킷 주소를 가리킨다

서로 다른 키 값이 동일한 버킷 주소로 변환된다면 충돌(collision)이 일어나며,

이 때 오버플로 버킷이 생겨난다면 해싱의 장점을 잃기 때문에 확장성 해싱으로 충돌에 대처한다

 

모조키와 확장성 해싱 초기 상태 (0비트)

확장성 해싱에 삽입 (분할되며 비트 수 증가/ppt 참고)

비트맵 인덱스

애트리뷰트의 값이 몇가지 되지 않을 때(소득수준, 성별, 국가 등) 비트맵 인덱스를 활용한다

 

각 애트리뷰트에 비트를 부여해 식별한다

비트맵 인덱스 질의 예시

인덱스 삭제시 존재 비트맵을 통해 삭제 기록을 남겨 대응 / 널 비트맵은 레코드의 NULL 값을 기록

지금처럼 하나의 키를 사용하는 파일들과 달리 다중 키 파일은 R-Tree를 사용한다

 

좌표 정보를 담은 GIS 데이터에 많이 사용

SQLite에서 인덱스 생성 및 삭제