인덱스 구조

인덱스의 개념

인덱스는 데이터 레코드를 빠르게 접근하기위해 구성하는 것입니다.

• 데이터가 저장된 물리적 구조와 관계가 있습니다.
• 레코드가 저장된 물리적 구조에 접근하는 방법을 제공합니다.
• 인덱스를 통해 파일의 레코드에 대한 액세스를 빠르게 할 수 있습니다.
• 레코드의 삽입과 삭제가 수시로 일어나면 인덱스의 개수를 줄이는게 좋습니다.

---

m-원 검색 트리(m-way Search Tree)

• 한 노드가 최대 m-1개의 키와 m개의 Subtree를 갖도록 구성됨
• 키 값의 일부분이 동일한 문자열이나 숫자로 구성된 자료를 표현하는데 좋음
• 트리 높이가 얕아져 특정 노드의 검색 시간이 감소됨
• 삽입, 삭제 시 트리 균형을 유지하기 위해 복잡한 연산이 필요합니다.

---

B-트리의 특징

Index를 구성하는 방법으로 가장 많이 사용하는 균형된 m원 검색트리입니다.

• Root와 Leaf(단말)을 제외한 노드들을 최소 m/2, 최대 m개의 Subtree를 갖습니다. 
• Root는 Leaf가 아닌 이상 적어도 두개의 Subtree를 가집니다. 즉 처음부터 분기해야합니다.
• 모든 Leaf는 같은 Level입니다.
• Leaf가 아닌 노드의 키 값 수는 그 노드의 Subtree 수보다 한개 적고, 각 단말노드의 수는 최소 m/2에 한개를 뺀것과 최대 m-1개의 키값을 가집니다.
• 한 노드 안에 있는 키 값들은 오름차순을 유지해야합니다.
• 탐색, 추가 삭제 는 루트로부터 시작합니다.
• 삽입과 삭제를 해도 데이터 구조를 유지 해야합니다.