인덱스(INDEX)

인덱스를 쓰는 이유

인덱스는 데이터 검색 속도를 높이기 위해 사용된다.

아래 테이블의 경우 

이름	나이	전화번호	아이디
kim	19	010-1234-5678	abc
kang	20	010-2345-2222	1234
lee	14	010-2312-2345	qwer

 

나이가 20살인 사람을 찾을 때 컴퓨터는 순차적으로 데이터를 하나씩 찾을 것이다. 데이터가 많이 없는 경우 찾는 속도가 빠르지만 데이터가 많아질수록 찾는 속도가 느려진다.

 

인덱스 사용

데이터베이스가 원본 데이터를 복사해 특정 순서로 정렬을 하여 인덱스를 생성한다(나이: 14, 19, 20) 최소한의 검색으로 데이터를 찾을 수 있다.  

 

인덱스를 구현하는 자료구조

클러스터(Clustered)

테이블의 데이터가 인덱스의 순서에 따라 물리적으로 정렬되어 저장된다. B-트리 구조에서는 리프 노드에 데이터를 저장하거나 포인터를 가리킨다.

 

장점: 데이터를 물리적으로 정렬했기 때문에 데이터 검색 속도가 빠르다.

단점: 데이터를 추가할 때 조건에 맞는 위치에 데이터를 저장해야 하기 때문에 추가 속도가 느리다.

 

논클러스터(Non-Clustered) 

인덱스와 데이터가 독립적으로 존재한다. 인덱스는 데이터의 위치를 가리키는 포인터를 저장한다. 

장점: 데이터 추가, 삭제 시 데이터의 재배치가 필요하지 않아 클러스터 방식에 비해 속도가 빠르다.

단점: 데이터를 찾기 위해서 인덱스를 통해 포인터를 찾고 실제 데이터가 저장된 위치로 접근해야 하기 때문에 클러스터 방식에 비해 검색 속도가 느리다.

 

B-트리구조

구조

노드: B-트리의 노드는 여러 개의 키와 그 키에 해당하는 자식 포인터를 가리킨다. 노드의 키는 정렬된 상태이다.
리프 노드: 자식 노드가 없는 노드이며, 데이터 레코드나 데이터 레코드에 대한 포인터를 저장한다.
내부 노드: 내부 노드는 리프 노드가 아닌 모든 노드로 다른 노드로의 포인터를 포함한다.
루트 노드: 트리의 최상위 노드로, 검색은 루프 노드에서 시작된다.

 

연산

검색: B-트리를 통한 검색은 루트 노드에서 시작하여 찾고자 하는 키 값보다 크거나 같은 첫 번째 키를 찾을 때까지 내려간다. 해당 키가 있는 노드를 찾을 때까지 이 과정을 반복한다.
추가: 적절한 리프 노드를 찾아 키를 추가한다.
삭제: 해당 키가 있는 노드를 찾아 삭제한다.