인덱스 톺아보기

By Gyumyung Lee
technology

인덱스 톺아보기

인덱스란?

인덱스란 테이블의 검색 속도를 향상시키기 위해 사용하는 자료구조로, 데이터와 데이터의 위치를 포함한 자료구조이다.

인덱스를 활용하면 데이터를 조회하는 SELECT 쿼리 동작 외에도 UPDATE나 DELETE 성능도 함께 향상된다. 데이터를 수정, 삭제하기 위해서는 해당 대상을 조회해야 하기 때문이다.

만약 인덱스를 사용하지 않은 컬럼을 조회한다고 하면 Full Scan을 수행하게 된다. Full Scan은 보통 테이블에 저장된 순서대로 전체를 비교하며 대상을 찾기 때문에 처리 속도가 떨어진다.

인덱스 관리

DBMS는 인덱스를 항상 최신 정렬된 상태로 유지해야 빠르게 탐색할 수 있다. 따라서 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음의 작업을 해줘야 한다.

  • INSERT: 새로운 데이터에 대한 인덱스 추가
  • DELETE: 삭제하려는 데이터의 인덱스를 사용하지 않게 작업
  • UPDATE: 기존의 인덱스를 사용하지 않고, 갱신된 데이터에 대한 인덱스 추가

인덱스 장점과 단점

  • 장점
    • 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
    • 전반적인 시스템의 부하를 줄일 수 있다.
  • 단점
    • 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
    • 인덱스를 관리하기 위해 추가 작업이 필요하다.
    • 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

만약 INSERT, UPDATE, DELETE 가 빈번하게 발생하는 컬럼에 인덱스를 사용하게 되면 오히려 성능이 저하되는 역효과가 발생할 수 있다. UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 사용하지 않게 처리하는 작업을 하기 때문에 인덱스가 점점 많아져 비대해지기 때문이다.

인덱스를 사용하면 좋은 경우

  • 규모가 작지 않은 테이블
  • INSERT, UPDATE, DELETE 가 자주 발생하지 않는 컬럼
  • JOIN 이나 WHERE, 또는 ORDER BY에 자주 사용되는 컬럼
  • 데이터의 카디널리티가 높은 (중복도가 낮은) 컬럼

인덱스의 구조

일반적으로 자주 사용하는 B+Tree 인덱스 구조에 대해 알아보자.

우선 그 전에 B-Tree 자료구조에 대해 알아보자면 N개의 자식을 가지는 트리 구조이며, 좌우 자식 간의 균형이 맞지 않은 경우 매우 비효율적이라 항상 균형을 맞춘다는 의미에서 균형 트리 (Balanced Tree) 라고 불린다. B-Tree는 최상위에 단 하나의 노드만이 존재하는데, 이를 루트 노트 (Root Node) 라고 한다. 그리고 중간 노드를 브랜치 노드 (Branch Node), 최하위 노드를 리프 노드 (Leaf Node) 라고 한다.

B-Tree 자료구조를 조금 더 알아보면

B-Tree는 Balanced-Tree를 의미하며 하나의 노드에 하나의 데이터를 저장하는 다른 Tree와는 달리, 하나의 노드에 여러 개의 데이터를 저장하는 방식으로 Tree의 height를 줄여 탐색 시간을 더욱 줄이도록 고안된 트리이다. 이러한 B-Tree의 형태를 유지하기 위해 몇 가지 규칙이 있다.

  1. 노드 안의 데이터는 정렬되어야 한다.
    한 노드 안의 데이터는 오름차순으로 정렬되어야 한다.

  2. 자식 노드의 데이터는 부모 노드의 데이터에 따라 배치된다.
    부모 노드의 데이터를 기준으로 자식 노드를 정렬하여 나눈다.

  3. 루트 노드가 리프 노드가 아닌 경우 항상 2개 이상의 자식을 갖는다.

  4. M차 B-Tree라면 루트 노드와 리프 노드를 제외하고 최소 M/2개 이상의 데이터를 가지고 있어야 한다.
    노드가 가질 수 있는 최대 자식 수를 M이라고 할 때, 이를 M차 B-Tree라고 한다.

B+Tree 자료구조

B+Tree 자료구조는 B-Tree의 확장된 버전이다.

B-Tree의 경우 브랜치 노드들의 데이터에 key와 value를 담을 수 있지만, B+Tree의 경우 브랜치 노드에는 key 데이터만 두고, value는 담지 않는다. 오직 리프 노드에만 key와 value를 저장하고 리프 노드끼리 Linked List로 연결되는 방식이다.

이러한 구조의 장점은 리프 노드를 제외하면 value 데이터를 담지 않기 때문에 메모리를 더 확보할 수 있다는 점이다. 또한 트리의 높이가 낮아지게 되며, 탐색 시 리프 노드의 데이터만 살피면 되기 때문에 B-Tree보다 탐색에서 매우 유리하다.

아래는 MySQL에서 사용하는 InnoDB 데이터베이스 엔진에서 사용된 B+Tree의 구조이다.

InnoDB 엔진에서의 B+Tree 구조는 일반적인 구조보다 조금 더 복잡한 형태이다. InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결된 형태이다.

인덱스의 동작 원리

인덱스의 저장 방식을 이해하려면 페이지 또는 블럭이라고 하는 것에 대해 알아야 한다. 페이지란 디스크와 메모리에 데이터를 읽고 쓰는 최소 작업 단위이다. 일반적으로 인덱스를 포함하여 PK, 테이블 등은 모두 페이지 단위로 관리된다. 즉 1개의 레코드를 조회한다 해도 최소한 하나의 페이지를 읽어야 한다.

따라서 페이지에 저장되는 각 데이터의 크기를 최대한 작게 유지하여 1개의 페이지에 최대한 많은 데이터들을 저장할 수 있도록 하는 것이 중요하다. 만약 레코드를 찾는 데 1개의 페이지만으로 처리가 안된다면, 추가 페이지를 읽는 I/O로 인해 성능이 떨어지게 된다. 이는 메모리의 효율을 위해서라도 중요하다. 결국 DB 성능 개선과 쿼리 튜닝은 디스크 I/O 자체를 줄이는 것이 핵심인 경우가 많다.

인덱스는 페이지 단위로 저장이 되며, 인덱스 키를 바탕으로 항상 정렬된 상태를 유지하고 있다. 정렬된 인덱스 키를 따라서 리프 노드에 도달하면 (인덱스 키, PK) 쌍 형태로 저장되어 있다.

위 그림은 B-Tree 인덱스 영역 (왼쪽 녹색 영역) 과 Primary 키 인덱스 = 클러스터 인덱스 영역 (오른쪽 주황색 영역) 으로 나뉘어져 있다. User의 name 컬럼에 인덱스가 적용되어 있는 경우, B-Tree 인덱스에서 인덱스 키가 name 값을 기준으로 정렬되어 있고 데이터를 따라 리프 노드에 도달하면 인덱스 키에 해당하는 레코드의 PK 값이 저장되어 있다.

인덱스는 테이블과 독립적인 저장 공간이므로 인덱스를 통해 데이터를 조회하려면 PK를 찾아야 한다. B-Tree 인덱스 영역에서 클러스터 인덱스 영역으로 넘어가 PK로 레코드를 조회할 때는 해당하는 PK가 어느 페이지에 저장되어 있는지 알 수 없으므로 랜덤 I/O가 발생한다 (위 그림에서 루트 노드 부분). 이후 PK를 따라 리프 노드에서 실제 레코드를 읽어 온다.