Index란?

 데이터를 조회할 때 조회 속도를 향상시키기 위한 자료구조이다.
테이블의 모든 데이터를 조회하게 되면 오랜 시간이 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조(index)를 생성하여 빠르게 조회할 수 있게 한다.
인덱스는 크게 단일단계 인덱스와 다단계 인덱스로 나눠진다.

단일 단계 인덱스

1. 기본 인덱스

• 탐색키가 데이터 파일의 기본키(Primary Key)인 인덱스
• 하나의 필드는 기본키, 다른 하나는 해당 데이터의 위치에 대한 주소를 가지고 있으며 여러 레코드당 하나의 인덱스 엔트리를 가지는 구조를 가지고 있다.

2. 클러스터링 인덱스

• 논리적으로 관련된 데이터를 물리적으로도 디스크에 인접시켜 저장하는 인덱스

3. 보조 인덱스

• 정렬되지 않은 데이터 값을 탐색키로 가지지만 인덱스 테이블에서는 해당 데이터가 정렬된 채로 저장하는 인덱스
• 기본 인덱스와 비교시 순차 접근에 대해 비효율적이다.

다단계 인덱스

B tree 인덱스(Balance Tree Index)의 구조

• 최상위에 하나의 루트노드가 있고, 그 하위에 자식노드가 붙어있는 형태, 가장 하위 노트를 리프로드라고 하며 루트와 리프를 제외한 노드를 브랜치 노드라한다.
• 한 노드 당 자식 노드가 2개 이상이어야 하며 최대 3개의 자식 노드를 가질 수 있다.

B-tree 인덱스

• B-tree 인덱스의 경우 노드별로 데이터의 주소값을 가지고 있기 때문에 상대적으로 루트 노드에 가까운 값은 좀 더 빠르게 찾을 수 있다.
• 한 데이터의 검색은 효율적이지만 모든 데이터를 순회하게 되면 모든 노드를 방문해야하기 때문에 비효율 적이다.

B+tree 인덱스

• B-tree와는 다르게 리프노드에서만 데이터를 저장하고, 리프 노드끼리는 Linked list로 연결되어있다.
• 모든 데이터를 순회하게 되면 리프 노드끼리 Linked list로 연결되어 있기 때문에 선형조회 만큼의 시간이 소모된다.

*추가

B-tree의 데이터 삽입과 삭제