B : 데이터 페이지들의 수 R : 페이지 당 레코드들의 수 D : 디스크 페이지를 read/write하기 위한 평균시간 파일 스캔 동등 검색 범위 검색 삽입 삭제 힙 파일 BD 0.5BD BD 2D 검색 연산 + D 정렬 파일 BD Dlog2B D (log2B + match page 수) 검색 연산 + BD 검색 연산 + BD 군집 트리 인덱스 1.5BD DlogF1.5B D(logF1.5B + match page 수) 검색 연산 + D 검색 연산 + D 비군집 트리 인덱스 BD(R + 0.15) D(1 + logF0.15B) D(logF0.15B + matched Records수) D(3 + logF0.15B) D(3 + logF0.15B) 비군집 해시 인덱스 BD(R + 0.125) 2D BD 4D..
[데이터베이스/Database] B+ 트리(Balance Tree)
한 노드의 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 큰 값으로 정렬되어 있음. 내부 노드: 인덱스 엔트리. 키값과 방향 지시자로 구성. 리프 노드: 데이터 엔트리(검색 키 값으로 정렬됨) 검색 과정: 루트 노드(메인 메모리에 상주)에서 검색 시작 -> 검색 값에 따라 해당 자식 노드로 분기 -> Leaf 노드에 도달하여 탐색 레코드를 찾음. B+ 트리 (Balanced tree in height) - 루트 노드에서 리프 노드로 가는 모든 경로의 길이가 동일한 인덱스 구조 - 탐색 키 값에 관계없이 검색 시간이 거의 일정 - 검색을 위한 디스크 IO 횟수는 root로부터 leaf에 도달하는 경로의 길이 - 모든 리프 노드들은 double linked list로 연결됨 - 범위 검색에 유용 - 범..
군집 인덱스(Clustered Index): 정렬된 속성으로 만든 인덱스. 최대 하나만 생성 가능. 비군집 인덱스(Unclustered Index): 정렬되지 않은 일반 속성으로 만든 인덱스. 여러 개 생성 가능 밀집 인덱스(dense index): 데이터 파일의 각 레코드마다 한 개의 데이터 엔트리를 가짐. 즉 모든 레코드를 인덱싱. 희소 인덱스(sparse index): 각 데이터 블록마다 한 개의 데이터 엔트리를 가짐. 데이터 블록 중 하나의 레코드만 인덱싱. 군집 인덱스에서는 대부분 희소 인덱스를 구축. 실제 데이터 파일이 인덱싱된 속성으로 정렬되어 있으므로, 인덱스를 통해 검색값이 어느 데이터 블록에 속하는지를 비교하여 검색. 희소 인덱스가 밀집 인덱스보다 크기가 적으므로 상대적으로 효율적. 비..
인덱스 목적: 찾고자 하는 레코드의 검색 속도 향상 - Digital Index: 모체 데이터(전체 데이터베이스)를 기반으로 search key(탐색 키) 값을 찾기 쉽도록 배열한 data entry들의 집합 - Data entry: 인덱스 파일에 저장된 레코드(탐색키 필드 + 주소 필드) - 탐색 키 값에 따라 정렬 - 범용적인 인덱스 구조: balanced 트리 - 모체 데이터가 추가/삭제/수정되면 각 인덱스에 반영되어야 함 복합 인덱스: 두개 이상의 속성으로 인덱스가 만들어지는 것 ex) 전공, 학년으로 인덱싱: 전공으로 1차 정렬, 학년으로 2차 정렬 Index의 data entry에 저장할 방식 ① k *: search key 값이 k인 실제 data record ② : rid는 k 값에 해당하..
페이지: 데이터를 읽고 쓰는 기본 단위 (대부분 4KB/8KB, 데이터베이스에서 주로 사용) 블락: 메인메모리와 디스크간의 데이터 입출력의 기본 단위. 몇 개의 페이지들로 구성. (운영체제에서 주로 사용) 데이터베이스 연산 처리시간 : 페이지들의 입출력 시간 + CPU 처리 시간 페이지의 입출력 시간이 CPU 처리 시간보다 훨씬 크므로 데이터베이스의 데이터를 빠르게 처리하기 위해서는 데이터의 입출력에 필요한 페이지 수를 최소화할 필요가 있음 데이터베이스는 여러 개의 파일로 구성 논리적으로는 테이블들로 구성, 물리적으로는 파일들로 저장 1) Heap 파일 (순서가 없는 파일) 동등검색(ex: 학번이 1234인 학생을 검색) 키(ex: 학번, 주민번호) : 평균적으로 전체 페이지의 절반을 검색 값을 찾은 후..
정규형(Normal Form, NF) : 릴레이션 스키마에 있는 함수종속의 유형에 따라 정규화된 정도를 등급으로 구별함 정규형 등급이 높아질수록 데이터의 중복이 적어지고 이상현상이 줄어듦 FD를 기반으로 하는 정규형 : 제1정규형 (first normal form: 1NF), 제2정규형 (second normal form: 2NF), 제3정규형 (third normal form: 3NF), 보이스-코드 정규형 (Boyce-Code normal form: BCNF) 그 외의 정규형 : 제4정규형 (fourth normal form: 4NF), 제5정규형 (fifth normal form: 5NF or PJNF)) 1) 제1정규형 (first normal form: 1NF) : 릴레이션에 있는 각 필드가 원..
함수 종속성(Functional Dependency : FD) : 일종의 무결성 제약조건(IC, Integrity Constraints)이다. 릴레이션 스키마 R이 있고 X, Y는R에 속한 속성들의 집합이며 공집합이 아니라고 가정했을 때, R의 인스턴스 r에서 r에 있는 모든 가능한 투플들의 쌍 t1과 t2에서 if t1.X = t2.X, then t1.Y = t2.Y 인 경우 'X가 Y를 함수적으로 결정한다'라고 말한다. 기호로는 X → Y라고 표기한다. * 즉, X → Y인 경우, 투플끼리 X가 같으면 Y도 무조건 같아야 한다. 키, 기본키, 수퍼키와 함수 종속 K: 키 속성 집합, Y: 모든 속성들의 집합, S: 속성들의 집합 K → Y : 키는 스키마에 있는 모든 속성들을 함수종속함 S → Y :..
중복성때문에 발생하는 문제(Anomaly) - 갱신 이상(update anomaly) 중복된 데이터 중 하나를 갱신할 때 나머지 다른 행과 불일치(inconsistency) 발생 - 삽입 이상(insertion anomaly) 어떤 데이터 값을 모르면, 입력이 어려운 경우 발생 어떤 정보를 저장하려면, 다른 정보도 같이 저장해야 하는 경우 발생 - 삭제 이상(deletion anomaly) 어떤 정보를 지우면, 다른 정보도 같이 상실되는 경우 발생 한 릴레이션 스키마가 자연스럽지 않은 속성들간의 연관을 억지로 함께 명시할 때에 중복 발생. 함수 종속 관계를 이용하여, 중복 여부를 판단할 수 있고 스키마의 정제가 필요함을 알 수 있음 키가 아닌 속성들간에 함수 종속관계가 있으면, 일반적으로 데이터의 중복 ..