Database Index

Database Index

데이터 베이스에서 원하는 데이터를 빠르게 찾기 위해 주로 사용한다. 1700만개 정도 있는 데이터 베이스에 원하는 값을 찾기란 쉽지 않은 일이다. 

 

인덱스는 일반적으로: 키 - value

 

인덱스를 사용하려면 저장공간이 추가로 필요하다. 하지만 테이블을 저장하는 것 보단 적은 공간이 든다. 그 이유는 위와 같이 일반적으로는 키 - vlaue 구조이고 테이블의 나머지를 사용하지 않는다. 

 

인덱스의 종류

Single level Orered Index

Single level Oredered Index는 텍스트 북에 위치한 인덱스와 비슷하다. 또한 value의 경우 pointers로 구성하여 

 

인덱스 파일안은 정렬되어 있기 때문에 원하는 인덱스를 가져오기 위해 이진탐색을 사용하여 빠르게 인덱스를 가져온다. 

 

Primary Index - Sparse

구조: index entry<K(i), P(i)>
K(i): Primary key

P(i): 물리적 블록, 레코드의 주소를 포인터 형식으로 갖고 있다. 

 

Indexes는 dense 또는 sparse이다. 

• desnse
  dense index에는 데이터 파일 안에 모든 검색 키값에 대한 index 항목을 갖고 있다. 
• sparse
  sparse index는 몇몇의 검색키에 대한 항목을(block, anchor) 갖고 있는다. 

단점

 

레코드의 삽입 그리고 삭제가 발생할 때 레코드를 전부 이동하거나 인덱스 파일도 변경해야한다. 

 

해결책

 

- 정렬되지 않는 overflow file을 사용한다. 

- overflow record의 연결 리스트를 사용하여 찾아갈 수 있게한다. 

 

Clustering Index - Sparse

많은 레코드가 ordering field에 대한 공통된 값을 가질 경우 사용할 수 있다. 이 경우 Data file을 Clustered file이라고 부를 수 있다. 파일 레코드의 경우 각 레코드에 식별되는 값 없이 키가 아닌 필드에 대해 정렬됩니다. 즉 non key일 때 주로 사용한다. 

Secondary Index

데이터 파일은 몇몇의 secondary indexes를 가질 수 있다. secondary index는 다른 인덱스를 돕는 보조 인덱스이며 레코드가 어디 위치한지만 알려주는 역할을 한다. 레코드가 어디에 위치해야할지 정하는 용도는 프라이머리 키가 한다. 즉 주키가 아니라 보조 키를 이용하여 추가적인 방법으로 원하는 값을 가져 올 수 있다.  

 

Dense Index이며 일반적으로는 더 큰 저장공간과 더 탐색시간이 오래걸린다. 

 

 

요약

Indexing field가 키라면 프라이머리 키를 사용하고 Indexing field가 키가 아니라면 Clustering index를 사용한다. 

 

Multilevel Indexes using ISAM

인덱스를 위한 인덱스를 만들어서 더욱 효율적이게 사용할 수 있다. 

 

Index file

multilevel index의 첫 레벨로 구성되어 있다. 

 

Second level

첫번째 레벨을 위한 primary index

 

Third level 

두번째 레벨을 위한 primary index

 

첫 인덱스를 제외한 나머지 인덱스들은 sparse여야 한다. 

 

 

Tree data structure terminology

- 트리는 노드들로 구성되어 있다. 

- 각 노드는 하나의 부모와 0개 또는 더 많은 아이 노드들을 가질 수 있다. 

- Leaf node는 자식을 갖지 않는다. 

- Nonleaf node는 internal node라고 부른다. 

 

E, J, C, G, H, K 는 leaf node

B tree

1. Search tree는 레코드를 위한 가이드 서치를 사용한다. 

- 주어진 레코드의 필드들 중 하나의 값

 

2. 트리에 검색 값을 삭제하고 삽입하는데 사용하는 알고리즘

 

3. 멀티 레벨로 structure에 제공된다. 

- 트리는 항상 균형적이며

- 각 노드는 2개 이상의 자식노드를 가질 수 있다. 

- 값은 정렬되어 있어야 한다. 

- 삭제로 인해 낭비되는 공간이 과도해지지 않는다.

- 각 노드는 반쯤 채워지거나 완전히 채워진채로 유지된다. 

- order p의 B tree 안의 각 노드는 최대로 p - 1 search values를 가질 수 있다. 

 

 

특정한 값을 찾는 경우 Log(n)의 탐색 시간이 걸린다. 

 

B+ Tree

데이터 포인터를 leaf node에만 저장한다. 

- leaf node는 search field의 모든 값에대한 항목 그리고 만약 search field가 key field이면 레코드를 위한 데이터 포인터를 갖는다. 

- 만일 키가 아닌 검색 필드의 경우 포인터는 데이터 파일 레코드에 대한 포인터가 포함된 블럭을 가리키게 된다.

- 또한 leaf node는 연결 리스트로 연결되어 있다. 

- B tree에 비해 level이 낮아져서 디스크 I/O가 현저하게 줄어든다. 

 

장점
leaf 노드를 제외한 다른 노드에는 데이터를 저장하지 않기 때문에 메모리를 더 확보하여 더 많은 키들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다. 

전체 leaf노드를 순회를 하면 leaf node가 n개 존재하기 때문에 (n)이 걸린다.  

 

 

삽입

자식 노드의 버킷이 꽉차있지 않다면 삽입

버킷이 꽉차 있다면 버킷을 나눈다. 

- 새로운 단말노드를 확보하고, 버킷에 구성 요소의 절반을 새로운 노드로 옮긴다. 

- 새 단말 노드의 최소 키를 부모로 이동한다. 

 - 만약 부모노드 또한 꽉차있다면 부도 노드 또한 나눈다. 쪼개지지 않는 부모를 찾을 때까지 반복한다. 

- 만약 루트가 쪼개졌으면 새로운 루트를 만드는데 1개의 키와 2개의 포인터를 가져야한다. 

 

 

 

삭제

루트에서 시작하여 삭제하려는 엔트리가 속해있는 노드를 찾는다. 

엔트리를 삭제한다. 

 - 노드가 절반이상 차있다면 종료한다. 

 - 절반이하라면 

 -- 형제가 절반 초과라면 재분배하고 엔트리를 빌려온다. 

 -- 형제의 엔트리들이 정확히 절반이라면 L과 형제를 병합한다. 

병합이 일어났다면 노드의 부모로 부터 삭제된 노드를 가리키는 포인터를 삭제한다. 

병합은 루트까지 전파되어, 트리의 높이를 감소시킬 수 있다. 

 

 

B Tree와 B+ 트리의 차이점

- B+ 트리의 경우 level이 훨씬 더 작아진다. 

- B+ 트리의 경우 링크로 연결되어 있다. 

- B 트리의 경우 리프 노드, internal node에 key와 데이터를 둘다 연결 할 수 있었다. B+ 트리의 경우 leaf node에만 넣을 수 있다.