분류 전체보기

[ADV_db]Chap 3. Indexing - B+Tree 추가내용들

# B+tree Extensions B+Tree File Organization 리프 노드에 포인터가 아닌 레코드 자체를 저장하는 방식 삽입/삭제/갱신이 일어나더라도 항상 Clustered된 상태를 유지하게 해준다. 레코드가 포인터보다 사이즈가 크기 때문에 리프 노드에 들어가는 레코드의 최대 수는 리프 노드가 아닌 노드들의 포인터 수보다 작을 수 밖에 없다. 따라서 공간 활용도가 중요한데 이를 위해서 가능한 많은 Siblings를 Split/Merge에 포함시키게 된다. 그 결과 m개의 sibling노드가 재분배에 참여한다면 각 노드마다 최소⌊(m-1)n/m⌋개의 엔트리를 가지게 된다. 하지만 이 경우 리프 노드에 있던 레코드가 노드 사이즈보다 커져서 Split을 해야한다면, 레코드를 이동 시키는 비용은..

[ADV_db]Chap 3. Indexing - B+tree 검색,삽입,삭제

# B+Tree 검색 루트 노드부터 검색하는 key값인 v보다 큰 key값이 나올 때까지 검색하다 같은 key값을 가지면, P(i+1)로 아니면 P(i)로 가서 리프 노드가 될 때까지 반복한다. 하나의 노드는 보통 하나의 디스크 블록 사이즈인 4kb로 한다. 따라서 보통 하나의 index당 크기는 40byte로 정하고 Fanout n은 100정도로 하는 게 보통이다. 그럼 key가 백만개 있다고 가정했을 때, log50(1,000,000) = 4 이므로 검색할 때마다 4개의 노드를 지난다. Composite key(복합키) 만약 key가 primary key가 아닌 경우, 유일성을 보장하기 어렵다. 이런 경우, (ai , Ap)식으로 복합키를 만들어 유일성을 보장할 수 있다. 하지만, 이러면 더 많은 I..

[ADV_db]Chap 3. Indexing - B+Tree 소개

# B+Tree B+Tree vs Sequential index B+Tree Sequential index 장점 1. 삽입,삭제 과정에서 알아서 재구성이 일어난다. 2. 성능 유지를 위한 전체 파일 재구성이 필요하지 않다. 1. 쉽다 ㅋ 단점 삽입,삭제 과정이 좀 더 오래 걸리고, 트리를 저장할 추가 공간이 필요하다. 1. Overflow Block때문에 파일이 커질수록 성능이 떨어진다 2. 주기적으로 재정비가 요구된다. B+Tree 특징 B+tree에서의 모든 데이터는 리프 노드에 들어있거나, 그 주소가 저장되어 있다. 따라서 리프 노드를 제외한 노드를 "인덱스 노드"라 부르고, 리프 노드를 "데이터 노드"라 부른다. 모든 리프 노드는 연결리스트로 연결되어 있고, 순서대로 정렬되어 있다. 그리고 모든 ..

[ADV_db]Chap 3. Indexing

# Basic Concept Index File(Index entries) 이런 Index File은 더 빠른 검색을 위해 사용된다. 따라서 검색 키와 포인터로 이루어져 있고, 원본 파일보다는 용량이 작다. 또한, 여러 검색 키마다 여러 인덱스를 저장할 수 있다. Search Key 여기서 말하는 Search Key는 그동안 배웠던 primary key,Candidate key,super key와는 다른 개념이다. 하나 이상의 속성으로 구성될 수 있다. 인덱스 파일에는 여러 종류의 검색 키에 대한 인덱스가 존재할 수 있다. 예를 들어, 책을 고를 때 작가,출판사,주제,제목 등으로 인덱스를 둘 수 있는 거처럼 말이다. Index의 기본적인 종류 Ordered Indices Search Key에 따라 정렬된..

[ADV_db]Chap 2. 데이터 저장 장치 구조-2

# 레코드 저장 방법 Heap File Organization 빈 공간에 어디든 저장하는 방식 한번 할당받아서 저장된 레코드들은 움직이지 않는다. 중요한 문제는 Free Space를 효과적으로 찾는 방법 Free-Space Map 파일의 블록 중에 빈곳을 표시해주는 데이터 구조 만약 하나의 블록이 3bit로 이루어져 있다고 한다면, 각 블록을 8로 나누면 비어있는 곳이 얼마나 있는지 알 수 있다. Second-Level Free Space Map 각 엔트리가 First-level Space Map의 4개씩을 나타낸다면 그 중 최대값만을 이용하여 빈곳을 탐색하는 시간을 더욱 줄일 수 있다. Sequential File Organization Search-Key를 기반으로 정렬하여 파일에 레코드를 저장한다...

[ADV_db]Chap 2. 데이터 저장 장치 구조

# 파일 구성 데이터베이스는 파일들로 이루어져 있고, 각 파일들을 여러 레코드들로 구성된다. 레코드는 여러 연속적인 필드로 이루어져 있다. 이 때, 파일의 레코드의 사이즈는 고정되어 있고, 레코드는 디스크 블록보다 작다고 가정해보자. ERROR 1 그렇다면 이런식으로 파일이 이루어져있을 것이다. 이 때 각 레코드의 크기를 170kb라고 하고 블록의 크기를 512kb라고 하면,한 블록 단위로 저장할 때 2kB씩 "Cross Block Boundaries"즉 레코드의 일부분을 잘라야 하는 문제가 생긴다. 이런 경우 블록 사이즈를 모두 채우지 않고, 온전한 상태의 레코드들로 채운 후 진행해야 한다. ERROR 2 중간의 레코드가 삭제된 경우, 저 부분을 채우기 위해 뒤에 있는 모든 데이터를 한칸씩 이동한다면,..