(데이터베이스) 인덱스 구조

트라이(Trie) 색인(index)

키 값을 직접 표현하지 않고 키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성하는 구조이다. 즉 전체 키 값의 길이보다 키 값들 사이에 별개의 전위(Prefix) 수가 작을 때 적합하다.

1. 가변 길이의 키 값을 효과적으로 나타낼 수 있다.

2. 삽입 및 삭제 시 노드의 분열과 병합이 없다.

3. 트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수 (Radix)에 의해 결정된다.

4. 키 값의 분포를 미리 예측할 수 있다면 기억장소를 절약할 수 있다.

5. 트라이의 크기는 나타내려고 하는 키 값의 기수와 키 필드 길이에 의해 결정된다.

출처 - https://coding-factory.tistory.com/234

B - 트리 색인

차수 m의 B-tree는 tree에 있는 각 Node는 최대 m개 최소 (m/2)개의 종속 tree를 가져야 한다.

이 조건에 의해 tree의 각 Node가 적어도 반 이상은 key값으로 채워져 있도록 한다. 따라서 종속 tree가 없는 Node가 발생하지 않고 key값이 가능한 효율적으로 종속 tree에 분배될 수 있도록 한다.

root Node는 최소한 두개의 종속 tree를 가져야 한다. (단 tree가 root만 있을 경우 종속 tree는 없다.)

이 조건에 의해 tree가 처음부터 분기하도록 한다.

모든 leaf Node는 같은 level에 있어야 한다. ( 즉 , 모든 leaf Node는 root로 부터 같은 거리에 있어야 한다.)

모든 leaf Node가 root로 부터 같은 거리에 있도록 하므로 tree가 거의 균형되게 하여 어느 leaf Node를 탐색하든 처리 횟수가 같도록 한다.

Node의 key값의 개수는 종속 Tree의 개수보다 하나 적으며 최소 (m/2)-1개, 최대 m-1개이다.

B* - 트리 색인

B-tree의 문제점을 보완하기 위해 B-tree를 변형한 구조.

즉, B-tree에서는 제한 조건을 유지하기 위해 삽입과정에서 분열과 삭제과정에서 합병등의 보조연산이 필요할다. B*-tree에서는 이런 보조연산을 감소시키려 했다.

B+ - 트리 색인

B-tree의 변형 구조로 index부분과 leaf node로 구성된 순차data 부분으로 이루어진다.

index부분의 key 값은 leaf에 있는 key값을 직접 찾아 가는데 사용하고 모든 key 값은 leaf에 나열된다. 즉, index 부분의 key 값도 leaf node에 다시 한번 나열 된다.

leafnodex는 순차적으로 linked list를 구성하고 있어서 순차적 처리가 가능하다.

출처 - https://m.blog.naver.com/PostView.nhn?blogId=kdy0573&logNo=220561840212&proxyReferer=https%3A%2F%2Fwww.google.com%2F