📌 개요

DB를 사용할 때 데이터의 양에 따라 실행결과의 속도가 차이가 나는 것을 알 수 있다. 이때 RDB의 인덱스를 잘활용하면 쿼리의 성능을 높일 수 있다. 또한 인덱스는 별도의 메모리 공간에 존재하는데 이때 사용되는 자료구조에 대해서도 알아보자.

📖 DB 인덱스

인덱스란 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료구조 이다. 특정 컬럼에 인덱스를 생성하면 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 인덱스가 생성되었다면 쿼리문에 인덱스 생성 컬럼을 WHERE 조건으로 거는 등의 작업을 하면 옵티마이저에서 판단하여 생성된 인덱스를 탈 수 있다.

인덱스에 저장되어 있는 데이터의 물리적 주소로 가서 데이터를 가져오는 식의 동작을 하여 검색 속도의 향상을 가져올 수 있다.

📚 인덱스를 사용할 때 장점과 단점

인덱스의 가장 큰 특징은 데이터들이 정렬 되어있다는 점이다. 이 특징이 장점이자 단점이다.

• 장점

  • 조건 검색 WHERE 절의 효율성 증가
    테이블 안에 데이터가 쌓이게 되면 테이블의 레코드(row)는 내부적으로 순서가 없이 뒤죽박죽으로 저장이된다. 이런경우 WHERE절에 특정 조건에 맞는 데이터들을 찾아낼 때도 레코드의 처음부터 끝까지 다 읽어서 검색 조건과 맞는지 비교해야한다.(풀 스캔) 하지만 인덱스 테이블 스캔 시 인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에 해당 조건에 맞는 데이터들을 빠르게 찾아낼 수 있다. (이것이 인덱스를 사용하는 가장 큰 이유이다.)

  • 정렬 ORDER BY 절의 효율성 증가
    인덱스를 사용하면 ORDER BY에 의한 정렬과정을 피할 수 있다. ORDER BY는 굉장히 부하가 많이 걸리는 작업이다. 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생하기 때문이다. 하지만 인덱스를 사용하면 이미 정렬이 되어 있기 때문에 가져오기만 하면 된다.

  • MIN, MAX의 효율적인 처리가 가능하다.
    데이터가 정렬되어 있기 때문에 레코드의 시작 값과 끝 값 한건씩 가져오면 되기 때문에 풀 스캔 후 찾는 것 보다 훨씬 효율적이다.

• 주의점

  • 인덱스는 DML에 취약하다.
    INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면 인덱스 테이블 내에 있는 값들을 다시 정렬을 해야 한다. 인덱스 테이블, 원본 테이블 이렇게 두 군데의 데이터 수정 작업을 해줘야 한다는 단점이 발생한다. 그렇기 때문에 DML이 빈번한 테이블보다 검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋다.

  • 무조건 인덱스 스캔이 좋지만은 않다.
    검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋지만 무조건 인덱스가 검색에 좋지만은 않다. 예를 들어 1개의 데이터가 있는 테이블과 100만개의 데이터가 있는 테이블이 있을 때, 100만 개의 데이터가 들어 있는 테이블에서는 풀 스캔보다는 인덱스 스캔이 유리하겠지만 1개의 데이터가 들어있는 테이블은 인덱스 스캔보다 풀 스캔이 더 빠르다.

  • 속도 향상을 위해 인덱스를 많이 만드는 건 좋지 않다.
    인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하다. 때문에 너무 많이 인덱스를 생성하면 하나의 쿼리문을 빠르게 만들 수 있지만 전체적인 데이터베이스의 성능 부하를 초래한다.
    

📖 인덱스의 자료구조

이러한 인덱스는 몇 가지 자료구조를 통해 만들어진다. 그 중 가장 대표적인 3가지인 해시 테이블, B-Tree, B+Tree에 대해 알아보자

📚 해시 테이블

해시 테이블은 key, value 형태로 데이터를 저장한다. key를 통해 값에 바로 접근하므로 검색 시 O(1)의 복잡도로 빠르게 데이터를 찾을 수 있다.

하지만 key의 등호 연산에만 유리하고 쿼리에서 자주 사용되는 부등호(범위) 연산에는 불리하다.

📚 B-Tree

B-Tree를 알아보기 전에 일반적인 Tree가 아닌 왜 B-Tree를 사용하는지 알아둘 필요가 있다.

일반적인 트리는 이렇게 생겼다. 하지만 어떤 데이터가 추가되고 삭제될지 모르기 때문에 이런저런 DML 작업을 당한 테이블은 이런 형태가 될 수 있다.

이렇게 한 쪽으로 편향된 트리는 검색을 위해 모든 노드를 순회 해야 하므로 검색 성능이 매우 떨어지게 된다.

그래서 데이터베이스에서는 B-Tree를 사용한다. B는 Balanced의 약자로 언제나 같은 높이의 트리를 유지하기 때문에 검색 성능을 유지 시킬 수 있다.

B-Tree는 아래와 같이 생겼다.

값을 찾기 위해서 일반적인 트리처럼 좌, 우측만을 사용하지 않고 노드에 저장된 값 사이의 포인터를 통해 탐색한다.

위 그래프에서 14라는 값을 찾는다고 하면 14는 7과15사에 있으므로 가운데에 연결된(9,11) 노드로 내려가고 14는 11보다 크므로 11의 오른쪽 노드로 내려가서 14라는 값에 도달하게 된다.

노드가 추가 되거나 삭제 될 때는 한 노드에 얼마나 많은 값들이 존재할 수 있는지 체크를 하고 값을 맨 아래 리프노드의 적절한 위치에 넣은 후 제 자리를 찾아가게 된다.

예를 들어 13이라는 값이 추가 되면 최초에는 (12,14)노드 사이에 들어간다. 하지만 위의 트리의 경우 한 노드에 2개 값만 존재할 수 있으므로 13이 한 단계 한 단계 레벨을 올리며 자기 자신의 자리를 찾아가게 된다.

이 과정을 페이징 이라고 한다.

📚 B+Tree

B-Tree는 데이터의 검색에는 유리하다. 하지만 모든 데이터를 풀 스캔하려면 모든 트리를 전부 방문해야 한다.

이러한 단점을 개선한 것이 B+Tree 이다.

B+Tree는 리프 노드에만 데이터를 저장하고 모든 리프노드를 링크드 리스트를 통해 연결한다.

이렇게 하면 리프노드를 제외한 루트, 내부 노드에는 데이터를 저장하지 않기 때문에 메모리가 남고 내부 노드는 더 많은 키 값을 저장할 수 있게 되고, 이는 트리의 높이가 낮아지므로 검색 속도가 빨라진다.

또 테이블 풀스캔을 하는 경우에도 리프 노드에 모든 데이터가 있고 모두 링크드 리스로 연결되어 있으므로 풀 스캔시에도 B-Tree 보다 유리하다. 범위 스캔을 하는 경우에도 링크드 리스트를 통해 효율적인 순차 검색을 할 수 있다.