DBMS: File Organization and Indexing

INTRO 🙌

저번 시간에는 Disk와 File 대하여 알아보았다.

이번 시간에는 File Organiaztion과 Indexing에 개념에 대해 알아보자.

직관 👀

Frequent operations

• scan (모든 tuples 탐색)
• sort
• equality/range search
• insert/delete tuples
• search by person name
• search by age, sal, or (age, sal)

File organizations와 indexes를 사용하여 이러한 처리에 대한 속도를 높일 수 있다.

File Organizations 🧿

Hash

n개의 buckets; 각 bucket은 pages들의 연결 리스트로, 각 tuple을 하나의 bucket으로 hash한다.

다르게 말하면, hash 파일을 구성하는 페이지들은 bucket 단위로 묶인다.

bucket 번호가 하나 주어지면 그 bucket에 해당하는 기본 페이지를 찾을 수 있는 것이 hash 파일 구조

가령, 파일이 name 필드에 대해서 hash가 되어있는 경우에 ‘Joe라는 이름의 학생 레코드를 찾아라’

Sorted

페이지 내의 데이터가 정렬되어 있는 파일구조를 말한다.

하나의 속성 혹은 여러 개의 속성 조합 (‘search keys’ or just ‘keys’)

Entity set or table에 존재하는 key와 다름

B+

Sorted file with a lot of pointers on top to direct search

Index 🎆

인덱스라는 자료 구조를 통해 원하는 레코드 정보를 빠르게 검색 가능

• 시스템 부하 ↓, 시스템 전체 성능 ↑

이러한 인덱스 값을 기반으로 하는 필드 = Search key라 한다.

단점

• Index를 위한 추가 공간 필요
• 데이터 多 –> 생성 시간 ↑
• INSERT, UPDATE, DELETE 多 –> 성능 크게 감소

1. Clustered vs Unclustered indexes

Clustered

• Index Page: (키값, 데이터 페이지 번호)

책으로 비유하자면 페이지를 알고 있어서 바로 해당 페이지를 펼치는 것

• 데이터 테이블 정렬 O –> Heap 영역 필요없이 테이블 자체가 잘 정렬된 index(목차)

테이블 데이터를 지정된 컬럼에 대해 물리적으로 재배열

• 테이블당 오직 한개 (i.e., primary key)
• 데이터가 테이블에 물리적으로 저장 되는 순서
  • 가령, id가 클러스터 형 인덱스 –> id 값 기준 정렬
• 별도의 공간을 필요 X

언제 사용?

• 데이터가 자주 업데이트 되지 않는 경우
• 항상 정렬된 방식으로 데이터를 반환해야하는 경우
• 읽기(검색, 탐색) 작업이 월등히 많은 경우, 이때 매우 빠르다.

특징

• 데이터 입력/수정/삭제 속도 unclustered 보다 느림
• 물리적 정렬 –> Unclustered 보다 검색속도 빠름

동작 원리

[숫자 12 검색]

1. 루트 페이지: 파일 그룹번호 1 –> 리프 페이지 1000 이동
2. 리프 페이지: 12, asdf5 검색 완료

Non-Clustered

• (키값, RID)

책으로 비유하자면 목차에서 찾고자 하는 내용의 페이지를 찾고나서 해당 페이지로 이동하는 것

• 데이터 테이블 정렬 X –> Heap 영역에 index(목차) 페이지 만들어서 관리

물리적으로 데이터를 배열하지 않은 상태로 데이터 페이지 구성

• 테이블 당 여러개의 인덱스 (남용 –> 시스템 성능 저하)
• 군집화(= 정렬) 되어있지 않은 인덱스 타입
• 물리적인 순서에 따라 데이터를 정렬 X –> 순서대로 정렬 X
• 저장되는 별도의 공간(약 10%)이 필요
  • 데이터 페이지를 건드리지 않고, 별도의 장소(heap 영역)에 인덱스 페이지 생성

• 루트 페이지(루트 레벨 인덱스 페이지)
• 리프 페이지(중간 레벨 인덱스 페이지): 데이터 위치 포인터(RID)

1. 루트 페이지: 데이터의 키값 비교 –> 리프 페이지 번호 검색
2. 리프 페이지: RID 정보로 실제 데이터 위치 이동

언제 사용?

• where절이나 Join절과 같이 조건문 활용 테이블 필터링 할 때
• 데이터가 자주 업데이트 될 때
• 특정 컬럼이 쿼리에서 자주사용 될 때

특징

• 데이터 입력/수정/삭제 속도 unclustered 보다 빠름
• 물리적 정렬 –> Unclustered 보다 검색속도 느림

동작 원리

[숫자 12 검색]

1. 루트 페이지: 파일 그룹번호 1 –> 리프 페이지 100 이동
2. 리프 페이지: 12 = (데이터 페이지, 오프셋) = (1000, 3)
3. 데이터 페이지: 1000의 3번째 컬럼 이동
4. 12, asdf5 검색 완료

2. Primary vs secondary indexes (기본/보조 인덱스)

• 두 인덱스 구조들은 데이터베이스에서 서로 분리된 객체
• 기본/보조 인덱스 안에 존재하는 인덱스 블록들은 정렬된 엔트리 보관
  • 인덱스 블록 안에 존재하는 엔트리들은 인덱스/검색 키에 대하여 정렬

Primary indexes

[인덱스 블록(왼쪽) | 데이터 블록(오른쪽)]

• 데이터 블록(= disk block) 안의 행들의 조직과 저장소에 영향 O
• 하나의 테이블에 대하여 오직 하나의 기본 인덱스
• 정렬되어있는 파일에 대한 기본 인덱스
  • 데이터 블록들 안의 행들 인덱스 키 정렬
• Primary/Unique Key O
• 중복 X

Secondary indexes

[인덱스 블록(왼쪽) | 데이터 블록(오른쪽)]

• 데이터 블록에서 실제로 조직화된 행들에 전혀 영향 X
• 테이블당 여러 개
• 정렬되어있지 않은 파일에 대한 인덱스
  • 인덱스 블록의 인덱스 키만 정렬
• Primary Key X
• 중복 O
• index가 data record의 모든 주소값을 가지고 있어야 한다.

3. B+ Tree Index

가장 널리 쓰이는, 트리 구조 인덱스

SEARCH

Insert/delete 처리는 \(log_F(N)\)의 비용이 발생한다 (F = fanout, N = # leaf pages/records/tuples)

Tree를 height-balanced하게 유지하면, equality and range-searches가 효율적으로 발생한다.

이를 위해, 최소 50% 비율로 공간 할당한다 (root 제외).

• 각 노드 entry 개수: \(d <= m <= 2d\)

여기서 d는 트리 order를 의미한다 (아래 예시 참조).

상기 예제에서, d=2라는 말은 각 entry 개수가 4개인 각 sequence set을 2개, 즉 절반을 채우는 것이다.

B+ Trees SEARCH 실습

예제 1. Typical order: 100 | Typical fill-factor: 67%. \(Average Fanout = 100 + 100 * 33/100 = 133\)

Typical capacities: \(Height 4: 133^4 = 312,900,700 records\)

\[Height 3: 133^3 = 2,352,637 records\]

Can often hold top levels in buffer pool: \(Level 1 = 1 page = 8 Kbytes\)

\[Level 2 = 133 pages = 1 Mbyte\] \[Level 3 = 17,689 pages = 133 MBytes\]

예제 2. Assume a file which has 950 thousands (that is, 950000) records. Assume also that we are indexing this file using a B+ tree. In this particular B+ tree, the average page has an occupancy of 100 pointers (that is, the tree’s average branching factor is 100). Assume further that the amount of memory set aside for storing the index is 150 blocks, and that all 950000 records of the above file reside on disk.

Assume no duplicate search key exists, given a search key K, compute the minimal number of disk I/O needed to retrieve the record with that search key. Explain your answer.

다음 leaf로 뻗어가는 pointer 개수: 100개

저장 가능한 memory block 개수: 150개

따라서, 950,000개의 block을 담기 위해서 최소 3개 높이의 트리가 필요하다; \(100^3 > 950,000\).

특정 block 탐색을 위해 필요한 가장 최소 disk I/O 개수는 트리 level 2까지 총 block 개수가 100개이므로, 그 100개 전부를 memory에 저장하고 level 3에서 운좋게 잔여 50개의 memory 용량을 초과하기 전에 찾아내는 시나리오일 것이다.

따라서, 가장 최소 disk I/O 개수는 1개이다.

B+ Tree 탐색 문제 중간고사 ★

INSERT

7과 14 사이에 8을 넣으려는데 공간이 없는 모습이다; 공간 있으면 end.

때문에, 상기 그림처럼 해당 leaf를 split하고, 숫자 5를 root로 복사하여 끊어진 pointer를 복구한다.

root가 4개 이상의 entry를 포함하고 있기 때문에, 중간 숫자인 17을 새로운 root로 올린다.

B+ TREE에서 INSERT를 한 최종 모습이다.

INSERT 문제 중간고사 ★

DELETE

B+ Tree 실습 예제

다음 시간에는 Basic RA Operations에 대해 알아보자.

---

Reference

Database Management Systems by Raghu Ramakrishnan and Johannes Gehrke

Relational Operators