데이터베이스 인덱스

인덱스 (Index)

인덱스란 데이터베이스 테이블에 대한 검색 성능의 속도를 향상시키기 위해 사용하는 자료구조이다.

마치 책에서 특정 부분을 찾을 때 목차를 활용하는 것과 비슷한 원리로 동작한다.

 

책에서 원하는 부분을 찾아 읽을 때, 처음부터 순서대로 읽는 것은 많은 시간이 걸릴 것이다.

그래서 목차를 확인하고 원하는 부분으로 직행하는 것이 더 빠르다. "인덱스"가 이런 방식으로 작동한다.

 

위 이미지는 PK 에 대한 인덱스를 생성한 모습이다.

 

인덱스는 Key 와 Pointer 쌍으로 구성된다.

• Key : 검색하려는 데이터의 값
• Pointer : 실제 데이터 레코드를 가리키는 포인터

그림에서 보듯이 인덱스 엔트리는 모든 레코드에 대해 생성되는 것이 아닌, 일정한 크기의 블록 단위로 생성된다.

 

그렇기 때문에 데이터 파일에서 원하는 레코드를 찾아가는 것보다 인덱스에서 원하는 레코드가 있는 블록을 찾아간 후 해당 블록에서 원하는 레코드를 찾는 것이 훨씬 빠르다.

 

특징

• 테이블 조회 속도를 향상시킬 수 있다.
• 인덱스는 항상 최신의 정렬된 상태를 유지해야 한다.
  • 삽입, 수정, 삭제 연산에 대해 최신 상태의 인덱스를 유지하기 위한 추가적인 작업이 필요하다.
• 인덱스를 관리하기 위해 DB의 약 10% 에 해당하는 저장공간이 필요하다.

 

인덱스를 사용하면 유리한 경우

인덱스는 항상 최신의 정렬 상태를 유지하고 있어야 하기 때문에 삽입, 수정, 삭제 연산에 대해서는 오버헤드가 발생한다.

따라서 항상 인덱스를 적용하는 것이 좋은 것은 아니다.

 

인덱스가 유리한 경우

• 테이블의 규모가 작지 않을 경우
• INSERT, UPDATE, DELETE 가 자주 발생하지 않는 컬럼
• JOIN, WHERE, ORDER BY 에 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼

---

 

인덱스 자료구조

인덱스를 구현하기 위한 자료구조로는 대표적으로 해시 테이블과 B+ Tree 가 있다.

해시 테이블

 

• 해시 테이블을 사용하면 빠른 데이터 검색이 가능하다.
• Key 를 통해 원하는 레코드를 O(1) 에 검색할 수 있다. (충돌이 일어나지 않았다면)
• 하지만 해시 테이블은 = 연산에만 특화되어 있기 때문에 특정 범위에 있는 데이터를 검색 하기는 힘들다.

B+ Tree

B+ Tree 는 B Tree 를 개선시킨 자료구조로 우선 B Tree 에 대한 이해가 필요하다.

 

B - Tree

• B-Tree 란 Balanced Tree 로 모든 리프 노드가 같은 레벨에 위치한다는 특징이 있다.
  • 데이터를 효율적으로 저장하고 검색하기 위해 고안된 트리 구조이다.
• 차수가 p 인 B-Tree 의 특징
  • 루트와 리프를 제외한 노드의 서브트리 수 : [p/2] ≤ 개수 ≤ p (적어도 노드의 반은 채운다)
  • 루트(리프가 아닌) 의 서브트리의 수 > 2 (루트 노드부터 분기)
  • 모든 리프는 같은 레벨 (균형 트리)
  • 카 값의 수 (노드내의 키 수)
    • 리프 : [p/2] - 1 ~ (p-1)
    • 리프가 아닌 노드 : 서브트리 수 - 1
  • 한 노드 내의 키 값은 오름차순으로 정렬

 

B+ Tree

• B Tree 와 비슷한 구조를 갖지만 B+ Tree 는 리프 노드만 실제 데이터를 갖는다는 점이 다르다.
• 인덱스 세트 : 내부 노드로 리프에 있는 키에 대한 경로 정보만 제공한다.
• 순차 세트 : 리프 노드로 모든 키 값들을 포함하고 있고 순차적으로 연결되어 있다.

 

인덱스의 자료구조로는 대부분 B+ 트리를 사용한다.

• B 트리 보다 더 빠른 검색 속도를 제공한다.
• 해시 테이블은 범위 검색이 불가능하지만 B+ 트리는 범위 검색에도 우수하다.

---

인덱스 종류

Clustered Index

• 클러스터드 인덱스는 데이터베이스 테이블의 실제 데이터 순서에 따라 정렬된 형태의 인덱스이다.
• 테이블당 하나의 클러스터드 인덱스만 가질 수 있다.
• 클러스터드 인덱스를 가진 컬럼의 값에 따라 데이터가 물리적으로 정렬되어 있어 검색 속도가 빠르지만 삽입, 삭제, 갱신 작업 시에는 성능이 영향을 받을 수 있다.
• 주로 검색이 자주 이루어지는 컬럼에 사용하면 효과적이다.

Non-Clustered Index

• 논 클러스터드 인덱스는 데이터베이스 테이블의 실제 데이터 순서와 상관없이 별도의 데이터 구조로 인덱스를 생성한다.
• 테이블당 여러 개의 논 클러스터드 인덱스를 가질 수 있다.
• 논 클러스터드 인덱스는 인덱스에 해당하는 컬럼의 값과 해당 레코드의 물리적인 저장 위치를 매핑하는 형태로 구성되어 있다.
• 클러스터드 인덱스 보다 느리지만 삽입, 삭제, 갱신 작업에는 더 효율적이다.
• 주로 검색과 데이터의 변경이 많은 열에 사용하면 효과적이다.