Index Structures

What is INDEX?

Why do we need it and What is it?

• 다양하고 방대한 블록들에 흩어져 있는 레코드를 표현하기란, 여간 간단한 일이 아니다.
  
• 모든 블록들은, 레코드의 시작과 끝, 그 레코드에 속하는 릴레이션이 무엇인지 알려주는
  '레코드 헤더' 에 대해 많은 정보들을 알고 있어야 한다.
  

'인덱스(Index)' 라는 자료 구조를 통해 원하고자 하는 레코드의 정보를 '빠르게'찾을 수 있다. 
또한 인덱스 자체도 물리적 구조이므로, 인덱스 데이터의 삽입/삭제도 꽤 복잡하다.
이런 인덱스 값을 기반으로 하는 필드를 'Search key(검색 키 혹은 탐색 키)' 라 한다. 
많은 다양한 인덱스의 구조가 있지만, 지금부터 살펴볼 내용은

1. Simple indexes : 정렬되어있는 파일에 대한 간단한 인덱스
2. Secondary indexes : 정렬되어있지 않은 파일에 대한 인덱스
3. B-trees : 가장 널리 쓰이는, 트리 구조 인덱스
4. Hash tables : 비트리와는 다르지만 또한 유용한 인덱스

Keys and More Keys

Key라는 건 더 많은 의미가 있다.
primary key, sort key 등...
Search key는 값이 주어지며, 
인덱스로 tuple의 matching-value를 찾기 위한 Column(s)를 말한다.

primary, sort, search등 Key의 의미가 명확하도록
이러한 표현들을 덧붙인다!

Indexes on Sequential Files

우선, 간단한 상황의 인덱스 구조에 대한 알아보자.
정렬된 파일인 Data file에게, Key-Pointer 쌍을 가지고 있는 Index file이 주어진다.
인덱스 파일 안의 Search key K는, 이 K를 보유한 Data file 레코드를
참조하고있는 포인터와 연관이 있다. 이러한 인덱스들은 기본적으로 두 가지로 구분할 수 있는데,

• Dense Index : Data file의 모든 레코드 항목이 존재하는 인덱스 구조.
• Sparse Index : 몇몇 데이터 레코드들만 표현되는 인덱스 구조. 보통 데이터 파일의 블록당 하나의 항목.

Sequential Files

• Sequential File : 인덱스의 Column(s)에 의해 정렬되는 파일.
  이러한 구조는 Search key가 릴레이션의 PK일 때 특히 유용하다(useful).

시퀀셜 파일에서는, 튜플들이 PK에 의해 정렬되어 있고,
그림과 같이 일반적으로 key를 10 and 20, 즉 10의 배수 상태로 구별한다

Dense Indexes

Dense Index

• Key와 레코드 자체에 대한 포인터만 보유하는 블록의 나열(인덱스).
• 'Dense(:밀집한)'라 불리는 이유는, 데이터파일의 모든 키가 인덱스에서 표현되기 때문이다.
• 덴스 인덱스는 Key들을 그 파일 자체 순서와 동일하게 유지한다.
• 키와 포인터만 보유한 인덱스는, 완전한 레코드보다 훨씬 적은 공간을 차지하기 때문에
  파일 자체보다 훨씬 적은 공간을 소모할 것이다.
• 즉, 인덱스는 데이터 파일을 위한다기보단, 메모리를 위해 설계된 것이다.
• 또한 인덱스를 사용하면, 1회의 Disk I/O 만으로도 주어진 Search key를 이용하여 어떤 레코드던 찾을 수 있다.

• Dense index는 인덱스 블록을 주어진 Search key 값 K로 검색하며, 찾을 경우 그 포인터로 연관된 레코드를 따라간다.
  
• 여.기.서
  K를 찾을 때까지 인덱스의 모든 블록을 탐색해야한다. (평균적으로 절반만큼)
• 성능이 좋아보이지 않지만, 인덱스 기반의 서치는 보기보다 효과가 대단하다.

Why?

1. 인덱스 블록의 수는 대개 데이터 블록의 수보다 비교적 적다.
2. 키값들이 정렬되어 있기 때문에 이진탐색을 할 수 있다. 인덱스에 n개의 블록이 있다면, log2(n)만큼이 소요
3. 인덱스는 메인 메모리 버퍼에 영구 유지될 수 있을 만큼 작다. 
   그렇다면 메인 메모리 액세스만 하면 되기 때문에 expensive한 disk I/O 수행이 필요 없다.

Sparse Indexes

Sparse Index

• Dense index는 모든 키를 가지고 있기에는 비교적 크다.
• 이런 단점을 보완하여 설계한 것이 바로 이 Sparse Index이다.
• 데이터 블록마다 오직 한 개의 Key-pointer 쌍을 보유한다.
• 훨씬 적은 공간을 사용하지만, 주어진 레코드의 key를 찾는데 더 많은 시간이 걸린다.
• 인덱스 블록만 보고, 찾고자하는 K가 존재하는 지 아닌지를 알 수 있는 Dense index와는 달리
  같은 쿼리문으로, Sparse index는 해당 블록에 K가 '있을지도 모르니' disk I/O를 요구한다.
  

• Sparse index는, 주어진 search key 값 K와 작거나 같은 값 중 가장 큰 값을 찾는다.
  
• 역시 인덱스 키 값들이 정렬되어 있기 때문에 이진 탐색이 가능하며, 찾을 경우 그 포인터로 연관된 블록을 따라간다. 
  
• 그 뒤로, key값 K를 찾기 위해 블록을 탐색한다. 
  물론 블록은 각 레코드의 컨텐츠가 식별될 수 있을만큼 충분한 정보를 가지고 있어야 한다.(저번에 살펴본)

Multiple Levels of Index

Multiple Level Index)

인덱스 자체로는, 많은 블록을 커버할 수 있다는 장점이 있지만, 
이진탐색으로 인덱스 항목을 찾더라도, 원하는 레코드를 찾고자 
여전히 수차례의 Disk I/O를 수행해야 할 수도 있다.
이럴 땐, 인덱스를 위한 인덱스를 둠으로 써, 인덱스를 좀 더 효율적으로 사용할 수 있다. 
 

• 그림은, 원래의 sparse index에 레벨을 하나 더 추가한 것이다.
  
  • 원래의 인덱스를 First level index(혹은 inner index),
    
  • 추가한 인덱스를 Second level index(혹은 outer index)라 한다.
    
  • 같은 아이디어로, third, fourth 등 계속해서 추가할 수 있다.

    
    
    

    
    
    

Warning

조그마한 주의사항으로, 
최초의 인덱스가 아니라면(최초의 인덱스는 dense/sparse 둘다 가능) 
반드시 sparse index여야 한다. (당연하게도..아니면 의미가 없어지므로) 

하.지.만 
이 원리는 한계가 존재하고, 많은 레벨의 인덱스들을 B-tree 구조로 빌드하는 것이 더욱 좋다. 

Indexes With Duplicate Search Keys

레코드의 Search key가 중복이 없다면, Dense index는 의미가 없을 수도 있다.

-> (모든 레코드의 값을 인덱스에 반영하므로)

하지만 대개의 경우, Search key의 중복이 여럿 발생하여 index를 배치한다.
이러한 중복을 해결하기 위해, 중복되는 Key값에 대해서는 한개의 인덱스 항목과 포인터만을 두자.
즉, 

• Dense Index의 경우, 중복 Key들에 대해 첫 번째 Key 값에 대해서만 인덱스 항목과 포인터를 두게 설계.
  
• Sparse Index의 경우, 블록당 한 개의 인덱스 항목과 포인터를 두며, 그 포인터는 항상
  블록의 첫 번째 Key 값만을 가리키게 설계.

Managing Indexes During Data Modifications

지금까지는 고정된, 정렬된 데이터 파일에 대해서만 인덱스를 살펴보았다. 
하지만, 데이터는 시간이 지남에 따라 발전하기 때문에, 레코드는 삽입/삭제/갱신될 수 있다. 
앞으로는 Sequential File(순차적 파일)같은 구조도, 한 블록에 들어 맞는 것이 존재하지 않게(더욱 거대하게) 변할 것이다. 
저번에 알아봤듯, 데이터 파일을 재구성 하는 방법처럼, 다양한 기법을 사용해야 한다. 

1. Overflow block 생성/삭제 : 오버플로 블록은 스파스 인덱스에 존재하지 않고, 차라리 기본 블록의 확장으로 간주되어야 한다.
2. 오버플록 대신, 순차적인 정렬 하에 새로운 블록을 삽입할 수 있다.
   이 경우, 새로운 블록에 대한 항목을 스파스 인덱스에 추가해야 한다.
   즉, 데이터 파일의 삽입/삭제 시 발생한 문제들과 같은 현상이 발생할 가능성이 있다는 걸 염두하자. 
   (인덱스 역시 물리적 공간에 저장되어야 하기 때문)
   
3. 튜플을 블록에 삽입할 공간이 없으면, 인접 블록(Adjacent Block)에 끼워 넣을 수 있다.
   반대로 또 인접 블록이 너무 텅텅 비게 되면 Combined(병합)될 수도 있다.
   

하지만, 데이터 파일의 변경은 해당 인덱스의 빈번한 변경을 야기한다.
정확한 방법은, 인덱스가 덴스/스파스 인지, 그리고 위에 열거한 세 가지 방법 중 어떤걸 사용하는지에 달려있다.
기억해야 할 하나의 기본 원리는

• 인덱스 파일 자체도 파일의 나열(Sequential file)이다. 
  ( 키-포인터 쌍은 search key값으로 정렬된 레코드로 취급 ) 
  그러므로, 데이터 파일을 유지보수 하는 데 사용한 것과 동일한 전략을 사용할 수 있다. 
  

위의 표에 나와있듯, 우리가 숙지해야 할 것들은,

• 빈 오버플로 블록을 생성/삭제하는 것은 어떤 인덱스든 효과가 없다.
  덴스 인덱스의 경우, 레코드를 참조하므로 무의미하고
  스파스 인덱스의 경우, 참조하는 것은 오버플로 블록이 아닌 주 블록만 참조하기 때문이다.
  

• 빈 정렬된 블록을 삽입/삭제하는 것은 
  덴스 인덱스에겐 효과가 없지만, (마찬가지로 블록을 보는게 아니라 레코드를 보기 때문)
  스파스 인덱스의 경우 각 블록의 삽입/삭제에 따른 인덱스 삽입/삭제가 반드시 필요하다.

• 레코드의 삽입/삭제에 대해서는, 
  덴스 인덱스는 무조건 key-pointer 쌍이 같이 변경되지만
  스파스 인덱스는 그 레코드가 블록의 첫부분이냐 아니냐에 따라 update/none이 결정되기 때문에 물음표를 첨가했다.

• 레코드 끼워넣기도
  덴스 인덱스는 같이 가고,
  스파스 인덱스 역시 그 끼워넣는 부분이 블록의 어디냐에 따라 달라진다.

Secondary Indexes

여태껏 살펴본 '인덱스'들은, 'Primary Indexes'라고 할 수 있다. 
즉, 인덱스가 레코드와 직접적으로 연결되어 위치를 결정하기 때문인데,
다양한 쿼리문을 좀더 용이하게 하기 위해 대부분의 경우 한 릴레이션에 대해 여러 개의 인덱스를 두고자 한다.

예시)

students ( name, dept_name, grade, ... )

SELECT  name
FROM  students
WHERE  dept_name = 'Comp. Sci.';

 name이 PK인 students라는 릴레이션에서(인덱스는 name에 관련한 쿼리를 돕기 위해 name으로 생성하겠지만,
 dept_name이 컴공인 학생을 검색하고 싶을 때

 -> dept_name을 search key로 가지는 인덱스가 있다면 더 효율적인 검색을 할 수 있다.(보조 인덱스의 필요성)

이렇듯 Secondary Index(보조 인덱스)는, 다른 인덱스를 돕는, 말그대로 보조 인덱스이다.
주 인덱스와의 가장 큰 차이로, 이 보조 인덱스는 데이터파일 내 레코드의 위치를 결정짓지는 않는다는 것이다.
위치를 결정해주는 건 주 인덱스고, 보조 인덱스는 그저 레코드의 위치가 어딘지 알려주는 역할을 할 뿐이다. 

이 두 인덱스의 차이점은, 

• 보조 인덱스로 스파스 인덱스를 사용하는 건 말도 안된다. 
  보조 인덱스는 위치에 영항을 끼치지 않기 때문에, 인덱스에서 명시적으로 언급을 해야지만 레코드의 위치를 알 수 있다. 
  -> 즉, 보조 인덱스는 항상 덴스 인덱스이다.

Design of Secondary Indexes

Design

• 보조 인덱스는 덴스 인덱스이며 중복이 보통 발생한다. 
  
• Key-pointer 쌍의 key는 search key 이며, 유니크할 필요는 없다.
  
• 주어진 Key 값으로 항목을 찾기 위해, 인덱스 파일의 쌍은 Key 값에 의해 정렬된다.

만약 상위 레벨의 인덱스를 설계하고싶으면 그 인덱스는 스파스이다!

보조 인덱스와 멀티레벨 인덱스를 혼동하지 말자.

• 데이터는 정렬되어 있지 않아도 인덱스는 정렬되어 있다. 
  
• 20이 무려 세개나 있는데, 이렇게 보조 인덱스를 이용할 땐
  주 인덱스만 이용할 때보다 Disk I/O횟수가 오히려 더 많을 때도 있다.
  
• 하지만, 데이터 블록의 튜플들은 아마 다른 column(s)에 의해 정렬된 상태일 테니 
  우리가 순서를 조정할 수 없어 이 문제는 해결할 수 없다!

Indirection in Secondary Indexes

• 위의 그림처럼 보조 인덱스를 설계한다면,
  상당히 많은 공간의 낭비가 생길 수밖에 없다.
  
• 즉, 데이터 파일의 Search key 값이 n회 나타나면 인덱스파일에도 n회 기록될 것이다.
  
• 반대로, 특정 값을 가진 데이터 레코드에 대한 모든 포인터에 대해서, 키 값을 한 번만 쓴다면 더 나을 것이다.
  

B-Trees

What is B-Tree?

1~2 level의 인덱스도 쿼리의 속도를 많이 향상시켜 주지만,
실제 상용 시스템에서 더 널리 쓰이는 구조가 있다.
바로 'B-tree' 라 하는 데이터 구조이며,
이 중에서도 특정 변형 형태인 'B+tree'를 가장 많이 사용한다. 
이제 B-tree에 대해 설명할것이지만, Detail은 모두 B+tree로의 변형을 위한 것임을 염두하자. 

• B-tree는, 인덱스를 생성할 파일의 크기에 적절한 만큼의 인덱스 레벨을 자동으로 유지한다.
• 블록의 공간도 관리하여, 모든 블록은 꽉 차있거나 최소 절반 이상 차있게 된다. 오버플로블록은 필요없다.

The Structure of B-trees

Structure

이름에서 알 수 있듯 B-tree 구조는, 블록을 트리로 구성한 것이다. 
B는 'balanced'의 약자이며, 이 밸런스는 루트로부터 리프까지 모든 경로는 같은 길이라는 것을 의미한다. 
B-tree에는 보통 세 종류의 레이어 ( Root, leaves, intermediate layer )가 있다. ( 더 추가할 수도 있다 )

• Root : 루트 노드
• Leaf : 리프 노드 (트리의 외부 노드(External node))
• Intermediate layer : 루트와 리프가 아닌 중간 단계에 있는 노드

각 인덱스와 관련된 파라미터 n이 존재하며, 이 n은 B-tree의 모든 블록의 레이아웃을 결정하게 된다.

• 각 블록은 n개의 Search key 값과 n+1개의 포인터를 위한 공간이 존재한다.
• 리프 노드의 Key 값은 데이터 파일의 Key값이다. 이 Key값은 왼쪽에서 오른쪽으로 정렬되어있다.
• 루트에는 적어도 두 개의 포인터가 사용된다. 또한 모든 포인터들은 하위(자식) 노드를 가리킨다.
• 리프의 마지막 포인터는 그 다음 크기의 Key를 보유한, 바로 오른쪽의 노드를 가리킨다.

• 또한 리프 블록 내의 다른 n 개의 포인터들 중, 적어도 (1+n)/2(나머지 버림)개의 포인터들은 데이터 레코드를 가리킨다. 
  (안쓰이는 포인터는 널을 의미하며 아무데도 가리키지 않음)
  

• 또한 i번째 포인터는 데이터의 i번째 key를 보유한 레코드를 가리킨다.

• 중간 노드들의 모든 n+1개의 포인터들은 그 다음 하위의 B-tree 블록을 가리킨다. 
  적어도 (1+n)/2(올림)개의 포인터가 사용된다.
  

Lookup in B-Trees

B-tree 인덱스를 가지고, Search-key K를 보유한 레코드를 찾는 작업을, 'Lookup' 이라 칭한다. 
K를, 루트부터 리프까지 Recursively(재귀적)으로 찾는다.

• BASIS : leaf에 도달하면, 거기서 key를 보자. i번째 key K라면, i번째 포인터가 레코드를 가리키고 있을 것이다.
• INDUCTION : 중간 내부 노드 (K1, K2, ... Kn)라면 원하는 key값 K를 찾아 child로 내려간다. 이 내려가는 절차를 재귀로 적용한다.

Range Queries

B-tree는 search key의 단일 값이 요구되는 쿼리문 뿐만 아니라,
값의 범위를 요구하는 쿼리문에서도 유용하다.
'Range queries' 는 WHERE 절에 '=' 나 '<>' 를 제외한 비교 연산을 이용하여 search key 값(들)을 비교하는 형태를 일컫는다.

예 :

SELECT  *
FROM  R
WHERE  R.k > 40;

or

SELECT  *
FROM  R
WHERE  R.k >= 10 AND R.k <= 25;

• [a, b]범위 내 모든 key를 B-tree의 리프에서 찾으려면, 먼저 a를 찾는다.
• a가 있든 없든 a가 있어야 할 위치를 알게 될 것이고, a가 있다면 a부터, a가 없다면 a보다 큰 제일 작은 값부터 범위 내에서 찾기 시작한다.
• 즉, 계속해서 다음 리프를 찾아가다가 마침내 b보다 큰 값을 보유한 노드를 찾게 되면, 그 지점에서 멈춘다.
• a가 마이너스 무한대여도, b가 무한대여도 (바운더리가 없다는 뜻일 뿐이므로) 충분히 가능하다.

Insertion Into B-Trees

Insertion

앞전에서, simpler multilevel index는 한계가 존재하여 B-tree로 구성하는게 좋다고 했는데
재귀에 따른 삽입 과정을 보며 그 이유를 살펴보자.

• 새로운 Key가 위치할 적절한 리프 노드를 찾고(lookup), 그곳에 공간이 있으면 넣는다.
  
• 오버플로가 발생하면, Split(리프 노드를 두 개로 나누고), 
  이 두 노드에 원래 보유했던 Key를 나눈다((1+n)/2 올림 까지)
  그러면 각 두 노드는 절반이 차거나 아니면 절반 조금 넘거나 할 것이다.
  
• 그리고선, 부모에 중간값을 올린다. 부모에 중간값이 들어가는 것 자체도 삽입 연산으로 취급한다.
  
• 예외적으로, 루트에 삽입하려고 했는데 공간이 없어서 분할한 경우,
  이 두 노드를 자식으로 갖는 새로운 루트 노드를 상위 레벨에 생성한다.
  (루트 노드는 slot의 개수와 상관 없이 한 개의 key를 갖고 두 개의 자식을 갖는다.)
  

노드를 분할하고 부모로 삽입할 때마다 키 관리는 무척 조심스럽게 해야한다.

먼저, n개의 슬롯을 가진 리프 N을 가정하자.(슬롯은 다 꽉찬상태)
그리고 이 리프에 n+1번째 key를 삽입한다고 가정해보자.
그럼, N을 나눠 새로운 노드 M을 N 바로 오른쪽에 만든다.
첫번째 부터 (1+n)/2까지의 key-pointer쌍은 N에 그대로 두고,
나머지 쌍들은 M에 옮긴다. (여기서, 적어도 (1+n)/2개의 쌍을 가져야 한다는 걸 주의하자)

< 파일첨부 >

Deletion From B-Trees

Deletion

특정 Key값 K를 삭제하려면, 일단 레코드 위치를 찾고, 리프노드의 key-pointer 쌍에 대한 정보를 알아야 한다..
찾은 후 삭제를 했는데, 이때

1. 삭제가 발생한 노드가 최소한의 key-pointer쌍 개수 이상을 보유하고 있다면
   그대로 삭제 연산은 끝난다.
   

하지만, 삭제 전에 최소의 개수를 가지고 있었을 수도 있어서,
삭제 후 키의 개수 제약을 깰 가능성은 다분하다.

2. 만약 부족하다면, 다음의 두 가지 방법 중 하나를 사용하여 B-tree 상태를 유지할 수 있다.
   
   • N의 인접한 형제 노드 중 하나가 최소의 key-pointer 쌍 개수보다 많이 보유하고 있을 경우,
     한 쌍을 N에게 전해주고, key의 순서를 그대로 유지한다. 
     이 때엔, N의 부모 노드가 새로운 상황을 반영해야 할 수도 있다.
     즉, 예를 들어 N의 오른쪽 형제 노드 M이, key중 가장 작은 값을 N에게 넘겨주면
     N,M의 부모 노드에게 M의 smallest key 값을 올려준다.
     
   • N의 인접한 형제 노드 중 아무도 최소 개수보다 많이 보유한 노드가 없는 경우도 있다.
     이 때엔 근접한 형제노드 두 개를 하나로 Merge(합친 뒤), 부모와 잘 연결해 주기만 하면 된다. 
     (합쳐도 한 노드가 가질 수 있는 최대 key-pointer 쌍의 개수보다 작거나 같으므로)
     부모가 삭제되어 또 최소 갯수를 만족하지 못한다면 이 알고리즘을 재귀로 돌려 부모 노드에서 시행한다.
     

<파일첨부>

Efficiency of B-Trees

B-tree는 레코드의 위치찾기(lookup)/삽입/삭제 면에 있어, 각 파일에 대한 disk I/O 횟수를 무척 줄여준다.
우선, 블록당 소유할 수 있는 key의 개수가 충분히 크면 Splitting / Merging같은 이벤트는 매우 드물게 된다.
일어난다 해도, 거의 대부분은 두개의 리프 노드, 그들의 부모 노드 정도만 영향을 받는다.
그러므로, I/O cost를 거의 무시할 수 있다고 봐도 과언이 아니다.

하지만, search key로 레코드에 대해 '검색'하는 것자체가 루트부터 리프 노드까지 포인터를 찾는것이다. 
즉, B-tree의 level 수만큼 disk I/O가 일어나고, 여기에 (lookup을 위한 1회), (insert/delete를 위한 2회) 
정도의 횟수가 더 발생한다. 

Hash Tables

Structure of Hash Table

해시 테이블 구조는,
search key를 인자로 받는 'Hash Function' 이 존재하고, 이 해시함수는 받은 search key 값을
'Bucket' (디스크 블록 같은 개념) 에 대응시킨다. (매핑한다)
즉, 레코드가 search key K를 보유한다면, 버켓넘버 h(K)번째 리스트 버켓에 링크 해놓음을써 저장한다. (h는 hash function)

Choice of Hash Function

'Hash function'은 key를 말그대로 'hash'할 수 있어야 한다.
또한 결과값이 정수형으로 나와야 한다는 게, 꼭 랜덤함수처럼 보인다.
이러한 해쉬함수는 보통 소수 bucket 수 B로 key 값 K를 나누는 형태를 띈다.
만약 search key가 문자라면, 문자들을 다 숫자로 치환해 더한 값을 B로 나누는 식으로 시행한다.

Insertion Into a Hash Table

Insertion

search key K를 가진 새로운 레코드가 삽입되면, h(K)를 수행한다.
h(K)번째 bucket에 공간이 있으면, 이 버킷의 블록에 레코드를 삽입한다.
만약 첫 번째 블록에 공간이 없으면 이 블록에 체인된 오버플로 블록 중 하나에 삽입한다.
(체인된 블록이 없다면 새로운 오버플로 블록을 만들고 그곳에 삽입)

Deletion from a Hash Table

Deletion

삭제도 같은 패턴이다.
버킷의 h(K)번째로 가 K로 삭제할 레코드를 찾고, 지운다.
만약 블록 사이에서 레코드의 이동이 가능하면 삭제 후
체인을 한 개 줄여 통합할 수도 있다 .

Efficiency of Hash Table Indexes

이상적으로, 각 블록을 알맞게 담을만한 충분한 크기의 버킷들이라면,

Key를 찾는데 1회의 Disk I/O, 
Insert / Delete는 2회의 Disk I/O밖에 하지 않는다.

이 횟수는 덴스/스파스/B-tree 인덱스 구조보다 현저히 낮은 숫자이다.
하지만, 파일이 점점 커지면 특정 버킷에 체인된 블록들이 주렁주렁 달리는 사태가 발생할 것이다.
따라서, 적어도 한 번의 Disk I/O가 발생하는 각 블록의 리스트가 아주 길어지면 좋을 것이다.
그러므로 버킷 당 블록 수를 낮게 유지할 필요가 있다.

우리는 지금껏 'Static Hash Tables(정적 해시 테이블)' 에 대해 살펴보았다. (버킷의 길이는 B로 고정)
이번엔 'Dynamic Hash Table(동적 해시 테이블)' (거의 모든 버킷들이 버킷 당 블록 하나씩만 매핑되게 유도가능한 해시 테이블)
에 대해 간단히 살펴보자.

1. Extensible hashing : 해시 테이블이 너무 작다고 느껴질 때, 두배 늘리는 기법
   
2. Linear hashing : 약간의 growing이 필요할 때, 매번 1씩 늘리는 기법
   

Extensible Hash Table & Linear hash Table

Extensible Hash Table(확장 해시 테이블)

1. 버킷에 Indirection level 도입. 즉, 데이터 블록 자체를 직접 포함하는 배열 대신, 버킷을 참조하는 블록에 대한 포인터의 배열을 둔다.
   
2. 포인터의 배열은 커질 수 있다. 그 길이는 항상 2배씩 커지며, 버킷 수도 2배씩 증가한다.
   
3. 그러나, 각 버킷당 데이터 블록이 반드시 하나씩만 있어야 하는 건 아니다.
   -> 해당 버킷의 총 레코드 개수가 블록 안에 들어갈 수 있다면, 특정 버킷들은 블록을 공유할 수도 있다.
   

Linear Hash Table(선형 해시 테이블)

1. 선형 해싱은, 해시 테이블이 한 번에 한 개의 슬롯씩 증가시킨다.
   
2. 슬롯 생성이 자주 일어나 효과적이지 않아 보이지만,
   이런 빈번한 싱글 슬롯 생성은 컬리젼 체인(Collision Chain) 길이를 조절하는 데 매우 효과적이다.

마침.