[Database System] File Organizations(1)
Database System
Why Organizing Files?
- 파일 조직(File Organization)은 파일이 디스크에 저장될 때 파일의 레코드를 배치하는 방법
- 레코드를 배치하는 다양한 방법은 효율적으로 수행할 파일에 대해 다양한 연산을 제공
- DBMS는 여러 파일 조직을 지원. 많은 대안이 존재하며, 각각은 일부 연산에는 적합하지만 다른 연산에는 좋지 않음
- DBA의 역할은 예상되는 사용 패턴에 따라 각 파일에 적합한 조직을 선택하는 것
Motivating Examples
- 전체 스캔이 필요한 SQL 쿼리를 보면
- 고객 레코드가 임의의 순서로 저장된다고 가정 → 힙(Heap) 파일로 저장
SELECT *
FROM customer
- 이 힙(Heap) 파일은 모든 고객 레코드 모음에 대해 효율적으로 전체 스캔을 지원함
- 하지만 이 힙 파일이 다음 쿼리를 효율적으로 지원하는가?
- 아니다 → 너무 느림
SELECT *
FROM customer
WHERE age = 40
- 다음 두 쿼리를 보면
SELECT cid, name
FROM customer
WHERE age > 40
SELECT cid, name
FROM customer
ORDER BY age ASC
- 위의 두 쿼리 속도를 높이기 위해 고객 테이블을 구성하는 방법은 무엇인가?
- 나이 값의 오름차순으로 고객 기록을 배치하고,
- 인접한 실린더에 기록을 둔다 → Seek time 감소
- (가능한 경우 레코드에 cid, name, age 필드만 포함)
- 파일 조직은 특정 쿼리를 효율적으로 만들기 위해 조정되지만 둘 이상의 쿼리 유형을 지원해야 하는 경우 문제가 발생할 수 있음
- 이 쿼리에는 cid 필드를 기준으로 정렬된 파일 조직이 필요
SELECT cid, name, age
FROM customer
WHERE 100 < cid < 9999
- 고객 테이블에 대한 파일을 age 로 정렬하면 위 쿼리에 전혀 도움이 되지 않을 수 있음
- 만약 이 쿼리가 매우 중요하고 고객 파일 조직에서 지원을 못받는 경우 지원 데이터 구조인 인덱스를 구축하여 이 쿼리의 속도를 높일 수 있음
Typical File Operations
- Scan: 파일의 모든 레코드를 읽음
SELECT *
FOMR R
- Equality Search: 파일에서 같음(=) 조건을 만족하는 레코드를 찾음
SELECT *
FROM R
WHERE A = 30
- Range Search: 범위(<, >, <=, .. ) 조건을 만족하는 레코드를 찾음
SELECT *
FROM R
WHERE A > 50
- Insert: 파일에 새로운 레코드를 삽입함
INSERT INTO R
VALUES < . . . >
- Delete: 파일에서 레코드를 삭제함
DELETE FROM R
WHERE A = 30
질문: 그렇다면 어떤 파일 구성이 가장 적합한가??
- 다음은 DBMS에서 지원하는 가장 일반적인 조직이다
- Heap Files: 레코드가 무작위로(특정 순서 없이) 보관
- Sorted Files: 레코드를 정렬된 순서로 보관
- Hashing Files: 해쉬 기능을 이용하여 기록을 보관
- Tree Indexed Files: 트리 인덱스를 사용하여 레코드를 보관
Hashing File
Hashing File
- 파일의 레코드는 primary 페이지와 overflow페이지의 chain으로 구성된 버킷(=페이지=블록)으로 정렬됨
- 레코드가 속한 버킷은 검색 값에 해시 함수를 적용하여 결정됩니다.
- h(X): 검색 값이 X인 레코드를 포함하는 버킷의 주소
Example: Hashing File
- primary 버킷에는 고객의 <이름, 나이, 급여> 레코드가 포함됨
- overflow 버킷이 없다고 가정
- 데이터 레코드는 ‘나이’에 대한 해시 함수 h에 의해 저장
- ‘나이’에 해시 함수 h를 적용하면 해당 레코드가 속한 버킷을 직접 찾을 수 있음
Hashing File (Contd.)
- 검색 값이 X인 레코드를 검색하려면
- 검색 값 X에 해시 함수 h를 적용
- 주소가 h(X)인 primary 버킷 페이지에 액세스하여 메인 메모리로 읽어들임
- 메인 메모리의 이 페이지에서 값이 X인 레코드를 검색
- (필요한 경우 overflow chain에 추가로 액세스)
- overflow chain이 없다고 가정하면 primary 페이지를 찾는 데 하나 또는 두 개의(디렉토리가 사용된 경우) 디스크 액세스만 허용
- 일반적으로 해싱 파일의 페이지는 80%로 채워져 향후 삽입을 위한 공간을 남기고 overflow를 최소화
- 오버플로가 없고 하나의 I/O가 있다고 가정하고 고급 해싱 파일에 대해서는 나중에 설명
Indexes
Concepts of Indexes
- 인덱스는 전체 파일을 스캔하지 않고도 데이터에 대한 효율적인 액세스를 지원하는 데이터 조직 → 인덱스는 검색 키 필드의 선택 속도를 높임
- 테이블의 모든 필드 집합(WHERE에 지정된 속성)은 테이블의 인덱스에 대한 검색 키가 될 수 있음
- 참고: 여기서 검색키는 후보키와 다름
Index: Index Entries
- 인덱스는 주어진 검색 키 값 K를 가진 많은 인덱스 항목 K*의 모음
- 인덱스 항목 K*로 저장되는 것은 무엇인가?
- 검색 키 필드 K가 있는 실제 데이터 레코드
- {K, 검색 키 값이 K인 데이터 레코드의 rid}
- {K, 검색 키 K로 데이터 레코드의 rid 목록}
- 여기서, rid는 검색 키 값이 K인 데이터 레코드를 포함하는 블록(페이지)에 대한 포인터를 의미
- Alternative 1
- 인덱스와 데이터(실제 레코드)가 함께 저장됨
- 이 Alternative는 pointer lookups를 저장하여 직접적인 접근을 함
- 주어진 데이터 레코드 모음에서 최대 하나의 인덱스가 대안 1을 사용할 수 있음 → 하나 이상일 경우 데이터 레코드가 중복되어 중복 저장 및 잠재적인 불일치
- 데이터 레코드가 너무 크면 인덱스 항목이 포함된 페이지 수가 많을 수 있음 → 인덱스에 있는 보조 정보의 크기도 일반적으로 크다는 것을 의미
- Alternatives 2 and 3
- 인덱스 데이터 항목은 데이터 레코드를 가리킴
- 인덱스 항목 크기는 일반적으로 데이터 레코드 크기보다 훨씬 작음
- 즉, 필요한 인덱스 페이지 수가 적음
- 특히 검색 키가 작은 경우 대용량 데이터 레코드가 있는 대안 1보다 좋음
- 대안 3은 대안 2보다 더 간결하지만 주어진 검색 키 값을 가진 데이터 레코드의 수에 따라 데이터 항목의 길이가 가변적
Index Entries : Hashing File
- 데이터 파일에는 고객의 <이름, 나이, 급여> 레코드가 포함
- 데이터 레코드를 ‘나이’에 대한 해시 함수 h1에 의해 저장
- 인덱스 항목은 실제 데이터 레코드 ← Alternative 1
- ‘나이’에 해시 함수 h1을 적용하면 해당 레코드가 속한 페이지를 직접 식별할 수 있음
- 데이터 레코드를 ‘급여’에 대한 해시 함수 h2에 의해 저장
- 인덱스 항목은 <급여, rid> ← Alternative 2
- 인덱스 항목 중 rid는 검색 키 값이 ‘샐러리’인 레코드를 포함하는 페이지에 대한 포인터
- 데이터 레코드를 ‘나이’에 대한 해시 함수 h1에 의해 저장
- 이 파일 조직은 연령 및 급여 검색 값에 대한 평등 검색을 효율적으로 지원
Primary/Secondary Index
- 검색 키가 기본(Primary) key를 포함하는 필드 집합인 경우 인덱스는 Primary임
- 다른 인덱스를 보조(Secondary) 인덱스라고 합니다. 대부분의 보조 인덱스에는 일반적으로 중복 항목이 포함되어 있음
- 대부분의 DMBS는 모든 관계에 대해 기본 키에 대한 인덱스(예: ORACLE의 unclustered B+ tree)를 자동으로 제공
- 기본 키가 포함되지 않은 검색 키에 자주 액세스하는 경우(예: join 작업을 위한 foreign keys) 사용자는 보조 인덱스를 명시적으로 제공해야 함
- 검색 키에 후보(candidate) 키가 포함된 경우 인덱스를 “unique”라고 함
Dense/Sparse Index
- 데이터 파일의 모든 검색 키 값이 인덱스에 있으면 인덱스가 밀집(Dense)됨
- 인덱스 데이터 항목은 각 데이터 레코드를 가리킴
- Dense index는 많은 공간을 차지하지만 존재하지 않는 테스트가 필요하지 않음
- 정렬되지 않은 데이터 파일은 밀집도가 높아야함
- 데이터 파일의 모든 검색 키 값이 인덱스에 있지 않은 경우 인덱스는 희소(Sparse)함
- 인덱스 데이터 항목은 각 데이터 페이지를 가리킴
- Sparse Index는 공간을 덜 차지하고 인덱스 검색은 더 빠르지만 부재(non-existence) 테스트가 필요
- Sparse Index는 디스크에 있는 데이터 파일의 고유한 물리적 순서(클러스터링)에 의존하기 때문에 파일에는 하나의 Sparse Index와 많은 Dense index가 있을 수 있음
Clustered/Unclustered Index
- 파일의 데이터 레코드 순서가 인덱스의 인덱스 항목 순서와 ‘동일’ 하거나 ‘가까운’ 경우 인덱스가 클러스터링되고(Clustered) 그렇지 않으면 클러스터링되지 않음(Unclustered)
- 인덱스는 데이터 레코드가 검색 키를 기준으로 정렬된 경우에만 클러스터링될 수 있음
- 데이터 파일에는 Clustered Index가 1개만 포함될 수 있지만 Unclustered Index는 개수에 제한이 없음
- Clustered Index는 연속 데이터 레코드가 동일한 페이지에 있기 때문에 빠른 범위 쿼리를 제공
- 그러나 연속 데이터 레코드가 다른 페이지에 상주하기 때문에 Unclustered Index가 더 느림
Clustered/Sparse Index : Key
Clustered/Sparse Index : Non-Key
Unclustered/Dense Index : Key
Unclustered/Dense Index : Non-Key
Indexing File : Exercise
- 고객 테이블
- 고객(아이디, 이름, 나이, 전화번호, 급여)
- 데이터 레코드 크기 = 100바이트, 고객 수 = 10^9개 레코드
- 검색 키 크기(ID) = 6바이트, 포인터 크기 = 4바이트,
- 블록 크기 = 1,024바이트. ID가 기본 키라고 가정
- 고객은 정렬되지 않음(힙(heap) 파일), dense index를 사용해야 함
- 블록당 데이터 레코드는 몇 개인가?
- 1024/100 = 10개 레코드/블록
- 데이터 블록은 몇 개인가?
- 10^9/10 = 10^8 데이터 블록
- 인덱스 항목 크기는?
- 6 + 4 = 10 바이트
- 블록당 인덱스 항목은 몇개인가?
- 1024/10 = 100 인덱스/블록
- 인덱스 항목의 개수는?
- Dense Index이므로 10^9 인덱스 항목
- 인덱스 블록은 몇개 인가?
- 10^9/100 = 10^7
- 주어진 아이디의 고객을 찾기위한 디스크 액세스 수는?
- 인덱스 파일에서 이진 검색(Binary Search): log2(10^7) = 15 액세스
- 인덱싱을 하지않고 주어진 아이디의 고객을 찾기위한 디스크 액세스 수는?
- 데이터 파일에서 순차 검색(Sequential Search): 10^8/2 = 50,000,000 액세스
- 블록당 데이터 레코드는 몇 개인가?
Index File : Exercise
- 고객 테이블, SQL 쿼리
- 고객(아이디, 이름, 나이, 전화번호, 급여)
SELECT 이름, 전화번호
FROM 고객
WHERE 나이 > 50
AND 급여 = 5000
- 고객은 ‘나이’별로 정렬, 그런 다음 두 개의 인덱스를 작성하여 이 쿼리에 효율적으로 답할 수 있음
- ‘나이’에 대한 Sparse/Clustered index
- ‘급여’에 대한 Dense/Unclustered index
- ‘나이’에 대한 인덱스를 사용하여 포인터를 찾음(나이 > 50인 모든 레코드)
- 그런 다음 ‘급여’에 대한 인덱스를 사용하여 포인터를 찾음(급여 = 5000 인 모든 레코드)
- 그런 다음 두 세트의 포인터를 교차하고 마지막으로 디스크에서 모든 정규화된 데이터 페이지를 가져옴
Multi-Level Index
- 인덱스 파일이 정렬되기 때문에 인덱스 자체에 대한 또 다른 인덱스를 생성할 수 있음
- 원본 인덱스를 1단계 인덱스라고 하고, 1단계 인덱스에 대한 인덱스를 2단계 인덱스라고 함과 같이 계속 진행
- 최상위 레벨의 모든 항목이 하나의 디스크 블록에 들어갈 때까지 이 과정을 반복
- Sparse index를 사용하여 i 번째 레벨 인덱스가 (i - 1) 레벨의 각 블록에 대해 하나의 항목을 갖도록 할 수 있음
- Multi-Level Index는 첫 번째 수준 인덱스가 둘 이상의 디스크 블록으로 구성되어 있는 한 모든 유형의 첫 번째 수준 인덱스(primary, secondary, dense, sparse)에 대해 생성할 수 있음
Two-Level Index : Clustered{: .text-center}
Multi-Level Index
- 각 페이지에 저장된 인덱스 항목의 수를 fan-out(F)-분기율이라고 함 F = B/Ri where B: block size, Ri: data entry size
- 각 상위 수준은 F 요인만큼 데이터 항목 수를 줄임
- F 값은 모든 지수 수준에서 동일
- r1 : 1단계 인덱스의 데이터 항목 수
1레벨: r1/F 블록 2레벨: r1/F2 블록 3단계: r1/F3 블록 . . . n 레벨: r1/Fn 블록 - 그러면 (r1/F^n) >= 1 따라서 검색 시간(n) = logF(r1)
Multi-Level Index : Exercise
- 고객 테이블
- 고객(아이디, 이름, 나이, 전화번호, 급여)
- 데이터 레코드 크기 = 100바이트, 고객 수 = 10^9개 레코드
- 검색 키 크기(ID) = 6바이트, 포인터 크기 = 4바이트,
- 블록 크기 = 1,024바이트. ID가 기본 키라고 가정
- 고객은 정렬되지 않음(힙(heap) 파일), Multi-Level index를 사용해야 함
- fan-out?
- 1024/10 = 100 인덱스/블록
- 1 단계 인덱스 항목의 개수는?
- 10^9 인덱스 항목
- 1 단계 인덱스 블록의 개수?
- 10^9/100 = 10^7 블록
- 2 단계 인덱스 블록의 개수?
- 10^7/100 = 10^5 블록
- 3 단계 인덱스 블록의 개수?
- 10^5/100 = 10^3 블록
- 총 인덱스 단계는?
- 5 단계
- 주어진 아이디의 고객을 찾기위한 디스크 액세스 수는?
- 인덱스 파일에서 이진 검색(Binary Search): logF(r1) = log100(10^9) = 5 액세스
- single level index에서 주어진 아이디의 고객을 찾기위한 디스크 액세스 수는?
- 데이터 파일에서 순차 검색(Sequential Search): log2(10^9) = 15 액세스
- fan-out?
댓글남기기