ch7) Indexing
Index란?
- 어떻게 하면 빨리 찾을까?
- 검색을 줄이기 위한 도구
ex) 학생 테이블을 주고 학생의 성적이 2.0이 안되는 학생을 다 찾아라 -> 민형이를 찾아라
관계 데이터 : 데이터와 데이터 간의 관계를 표현하는 데이터
ex) 학생이 수강한 교과목 목록
Index안에는 Simple Index, B+ tree, hasing 등등
1. 간단한 인덱스 구조부터 살펴봄
- (key, reference fields) 쌍으로 이루어진 간단한 배열을 이용한 인덱스
- ex) 책의 인덱스, library card catalog
2. 고정 길이 or 가변 길이 레코드 파일에 인덱스를 어떻게 적용?
3. 이후 예시에서는 대규모 음반을 가정함
- 기본 키(primary key)는 label + ID 형식 (ex : LON2312)
Simple Index
1. 첫 번째 column에는 key값, 두 번째 column에는 주소값을 저장
2. key에 대해서 sorting이 되어있어야함 (빠르게 찾기 위해서)
- Rocord address는 byte off 값임
- 단독으로 primary key를 정할 수 없을 때는 key들의 조합으로 primary key를 설정
ex) Label + ID => LON2312
- 사이즈가 작은 경우에 main memory에 올려서 사용
simple index를 파일을 저장할 때,
1. fixed-length vs variable-length record 중 선택
2. fied는 2개(key, addr) -> fixed or variable 중 선택
둘 다 fixed-length record, fixed-length fields 사용하는게 더 적합
Index파일을 만들고 유지보수 하기 위한 기초 연산
1. 인덱스와 데이터 파일 생성
2. memory 안에 index file을 로딩
3. memory에서 인덱스 파일을 수정하는 경우
- 레코드 파일에 새로운 레코드를 추가할 경우 (추가 후 맨 마지막 과정은 sorting)
- 레코드 파일의 레코드를 삭제할 경우
- 레코드 파일에 업데이트가 발생하는 경우 (key, refernce field가 변경되는 경우)
=> key값의 Label이 바뀌는 경우 sorting을 다시 해줘야 함
=> refernece field가 변경되는 경우는
(1) 변경된 record size가 커지는 경우
(2) reference field에 오래된 주소를 새로운 주소로 변경할 경우
Disk에서 Main memory에 올려놓고 사용하는 경우 -> index파일의 크기가 작아야함
만약, index 파일의 크기가 메인 메모리에 올리기에는 크다면 ?
=> 디스크에서 사용해야함으로 큰 비용 발생 (binary searching을 사용하더라도 -> several disk seeks 발생)
대안은?
1. hash table 사용
2. B+ tree 사용
Indexing to Provide Access by Multiple Keys
1. 주소값 대신 primary key를 사용함 (간접적으로 primary key에 해당하는 인덱스 파일을 찾을 수 있음)
-> 찾고자하는 Secondary key를 알면 이것을 통해 Primary key를 확인하고 이 primary key를 통해
simple index의 primary index의 byte offset 값을 확인하고 접근
단점 :
한번 더 거쳐가야함으로 비용이 많이 발생 (offset을 이용하면 바로 접근 가능)
장점 :
주소값이 바뀌는 경우에 byte offset값이 있다면 모든 값을 업데이트 해야줘야함.
(update 되는 경우)
하지만, primary key를 주소값 대신 사용한다면 인덱스 파일의 주소값만 변경해주면 됌
Secondary Index 의 파일 연산
1. Record Addition
- 데이터 파일에 새로운 레코드를 추가하면, secondary index에도 해당 레코드에 대한 항목을 추가
- secondary index의 순서 유지를 위해 기존 인덱스 항목들을 shift 해야 함.
=> Disk I/O 이 많이 발생(삽입된 레코드 이후의 모든 레코드를 한 칸씩 shift 해줘야 함으로)
2. Record Delection
- 해당 레코드에 대한 primary index 제거
- primary index를 참조하고 있는 모든 secondary index 제거
3. Record Updating
- secondary key를 변경하면, secondary index에서 해당 레코드를 재정렬 해야함
- primary key를 변경하면, secondary index 내부의 참조 필드만 수정
Retrieval Using Combinations of Secondary Keys
Improving the Secondary Index Structure
1. 기존 secondary index 방식의 문제점
(1) index file 재배열 필요
- 새로운 레코드가 추가될 때마다 secondary index를 정렬된 상태로 유지하기 위해 재배열이 필요
(2) secondary key field의 반복 저장
- 동일한 secondary key 값을 가진 여러 레코드가 있을 경우, 해당 키 값이 중복 저장되어 공간 낭비가 발생
=> Disk I/O 가 많이 발생(재정렬을 해야함으로)
2. 해결책
(1) array 사용
- 각 secondary key에 대해 1개의 엔트리만 저장
- 거기에 대응되는 primary key들의 배열을 연결
(2) 연결리스트 사용
- 각 secondary key에 해당하는 primary key들을 연결 리스트 형대토 연결
- 삽입이 빈번한 환경에서는 배열보다 리스트 방식이 더 유연
Using an Array
1. 구현이 간단
2. 문제점 :
(1) 배열이 꽉 차면, 추가 label IDs는 저장될 수 없음
(2) 공간 낭비가 내부 단편화를 발생시킴
(3) 배열을 작게 잡으면 새로운 공간을 재할당 해야하고, 너무 크게 잡으면 공간 낭비가 심함
Using an Linked List
1. secondary index를 재정렬하기 쉬움 (연결리스트는 삽입/삭제 시 위치만 바꾸면 되므로, 전체 재정렬 필요x)
2. 빠른 재정렬
- 각 레코드가 작고 적기 때문에 재정렬 작업이 빠름
- 특히 삽입 시 기존 요소를 shift할 필요가 없음
3. Label ID 리스트 파일이 순차적 ( 데이터를 삽입한 순서대로 저장함으로, 정렬할 필요가 없음)
4. 삭제된 공간 재사용이 쉬움
- fixed-length file이므로, 삭제된 레코드 자리에 새 데이터를 채워 넣는 매커니즘 구현이 쉬움
단점 : secondary 키 아래에 연결된 Label ID들이 디스크 상에서 연속 저장되어 있지 않을 수 있음
=> Seek 비용이 커짐
=> 새로운 노드를 추가할 때 맨 뒤의 노드를 찾고 저장해야해서 Disk I/O 비용이 많이 발생
-> 해결하기 위해서 reference index에 헤드값 뿐만 아니라 tail값도 저장 (바로 tail에 접근해서 추가할 수 있음)
ex) (3,1) 이런 식으로