티스토리 뷰
인덱스의 개념
- 인덱스(Index = 색인)는 데이터 레코드를 빠르게 접근하기 위해서 구성하는 것으로 다음과 같은 특징이 있음
＊ 인덱스는 데이터가 저장된 물리적 구조와 밀접한 관계가 있음
＊ 인덱스는 레코드가 저장된 물리적 구조에 접근하는 방법을 제공함
＊ 인덱스를 통해서 파일의 레코드에 대한 액세스를 빠르게 수행할 수 있음
＊ 레코드의 삽입과 삭제가 수시로 일어나는 경우에는 인덱스의 개수를 최소로 하는 것이 효율적임
m-원 검색 트리(m-Way Search Tree)
- 이진 검색 트리에서는 한 노드가 한 개의 키와 두 개의 Subtree를 갖는 반면 m원 검색 트리는 한 노드가 최대 m-1개의 키와 m개의 Subtree를 갖도록 구성됨
- m-우너 트리 구조는 키 값의 일부분이 동일한 문장려이나 숫자로 구성된 자료를 표현하는 데 효율적임
- 이진 검색 트리에 비해 트리 높이가 얕아져 특정 노드의 검색시간이 감소됨
- 삽입, 삭제 시 트리 균형을 유지하기 위하여 복잡한 연산이 필요해지는 단점이 있음
★ B-트리
B-트리는 Index를 구성하는 방법으로 가장 많이 사용하는 균형된 m원 검색 트리임
B-트리의 특징
＊ Root와 Leaf(단말)를 제외한 모든 노드는 최소 
＊ Root는 Left가 아닌 이상 적어도 두 개의 Subtree를 가짐. 즉 처음부터 분기해야 함
＊ 모든 Left는 같은 Level에 있음
＊ ★ Leaf가 아닌 노드의 키 값 수는 그 노드의 Subtree 수보다 한 개 적으며, 각 Leaf Node 수는 최소 
＊ 한 노드 안에 있는 키 값들은 오름차순을 유지해야 함
＊ 탐색, 추가, 삭제는 루트로부터 시작함
＊ 삾입과 삭제를 하여도 데이터 구조의 균형을 유지해야 함
B+-트리
＊ B+-트리는 B 트리의 변형으로 Leaf가 아닌 노드로 된 인덱스 세트와 리프 노드롬나 구성된 순차 데이터 세트로 구성됨
- 인덱스 세트에 있는 키 값은 리프 노드에 있는 키 값을 찾아갈 수 있는 경로로만 제공된다
- 인덱스 세트에 있는 모든 키 값이 리프 노드에 다시 나타나므로 리프 노드만을 이용한 순차 처리가 가능함
- B+- 트리는 B- 트리의 추가, 삭제 시 발생하는 노드의 분열과 합병 연산 과정을 줄일 수 있는 트리 구조임
＊ B+- 트리의 특징
- Root는 0, 2 또는
- Root와 Leaf를 제외한 모든 노드는 최소
- 모든 Leaf는 같은 레벨에 있음. 즉, Root로부터 같은 거리에 있음
트라이(Trie) 색인
- 트라이 색인은 탐색을 위한 키 값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 구조임
＊키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 때 적합함
＊가변 길이의 키 값을 효과적으로 나타낼 수 있음
＊삽입 및 삭제 시 노드의 분열과 병합이 없음
＊트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수(Radix)에 의해 결정됨
＊키 값의 분포를 미리 예측할 수 있다면 기억장소를 절약할 수 있음
＊트라이의 크긴느 나태내려고 하는 키 값의 개수와 키 필드 길이에 의해 결정됨