[Database] Index

Seongje kim, 18 October 2020

데이터베이스 인덱스에 대한 내용입니다.

인덱스(Index)

색인을 뜻하는 인덱스는 데이터베이스의 조회 및 검색을 더 빠르고 효율적으로 할 수 있도록 일종의 주소록 역할을 한다.

일반적으로 SELECT 문을 사용하여 원하는 조건의 데이터를 조회하려 할 때, 메모리 상의 데이터베이스 캐시에 저장되어 있는 테이블의 데이터가 아니라면 실제 하드 디스크의 모든 블록 테이블을 스캔하여 원하는 데이터를 조회해야 한다. 이때, 조회하려는 데이터의 위치를 먼저 알 수 있다면 순차 탐색에 소모되는 비용과 시간을 절약할 수 있을 것이다.

따라서 인덱스를 잘 활용하면 데이터베이스 조회 성능을 향상시킬 수 있다.

인덱스 테이블

인덱스는 하나 혹은 여러 개의 컬럼에 대해 설정할 수 있으며 따로 테이블 형태로 관리된다. 결국 인덱스를 설정하고 인덱스 테이블을 관리하는데 있어서, 그 개수에 비례하여 추가적인 메모리가 필요하다는 것이다. 그러므로 무조건 인덱스 많이 설정하는 것이 데이터베이스 성능을 향상시키는 것은 아니다.

따라서 인덱스를 설정할 컬럼을 선택할 때, 조회시 자주 사용되며 고유한 값(중복이 적은) 위주로 선택하는 것이 좋다.

B-트리와 B+트리

일반적으로 DBMS의 인덱스 관리는 B+트리를 활용한다. B+트리는 B-트리의 확장 개념으로 B-트리의 특성상 색인 구조에서 순차 접근 문제에 대한 해결책으로 제시된다.

B+트리는 인덱스 노드와 데이터 노드(레코드)로 구성되어 있으며 데이터 노드는 리프 노드에 해당한다. 또한 특정 키값이 하나의 노드에만 존재할 수 있었던 B-트리와 달리 특정 키값이 리프 노드와 부모 노드에 공존할 수 있다. 그 이유는 B+트리의 인덱스 노드(내부 노드)들은 데이터의 빠른 접근을 위한 인덱스 역할(키와 포인터만으로 구성)만을 수행하기 때문이다.

반대로 데이터 노드들은 키와 함께 실제 데이터(디스크에 존재하는 데이터의 주소값)를 가지고 정렬된 상태를 유지하며, 연결 리스트 형태로 서로 연결되어 있다. 결과적으로 B+트리의 색인 구조는 B-트리를 기반으로 데이터 노드까지의 경로들과 데이터의 연결 리스트로 구현된다.

B+트리의 장점

  1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 한 내부 노드에 수용할 수 있는 키의 개수가 증가하게 된다. 그 결과, 전체 트리의 높이가 낮아지면서 디스크 접근 횟수 및 시간이 절약되고 Cache Hit 비율을 높일 수 있다.

  2. 전체 데이터 스캔 시, 데이터가 리프 노드에만 존재하며 순차적으로 연결 리스트를 이루고 있기 때문에 한번의 선형 탐색만을 요구한다.

  • 그림/내용 참조