데이터베이스 인덱스 맛보기

🟩 랜덤 I/O와 순차 I/O

랜덤 I/O와 순차 I/O는 하드 디스크 드라이브의 원판을 돌려서 읽어야 합니다. 이때 데이터가 저장된 위치로 디스크 헤더(disk arm)를 이동시켜 데이터를 읽습니다. 순차 I/O는 디스크 헤더를 한 번만 움직이면 됩니다. 하지만 랜덤 I/O는 디스크 헤더를 데이터의 개수만큼 움직여야 합니다. 이처럼 랜덤 I/O는 읽을 데이터가 물리적으로 불연속하게 위치하기 때문에 순차 I/O에 비해서 작업에 더 큰 부하가 생깁니다.

일반적으로 쿼리를 튜닝한다는 말은 랜덤 I/O 자체를 줄여주는 것이 목적입니다. 즉, 랜덤 I/O를 줄인다는 것은 쿼리를 처리할 때 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미합니다.

 

디스크 성능은 얼마나 많은 데이터를 한 번에 기록하는가로 결정됩니다.랜덤 I/O와 순차 I/O 모두 파일 쓰기 작업을 할 경우 동기화 작업이 필요합니다. 순차 I/O라고 해도 동기화 작업이 빈번하면 랜덤 I/O처럼 비효율적으로 처리하게 됩니다. 그래서 캐시 메모리가 존재하는 RAID 컨트롤러를 사용해 순차 I/O를 효율적으로 처리할 수 있도록 도와주고 있습니다.

 

🟩 인덱스를 사용하는 이유는 뭘까?

데이터베이스는 어떤 데이터를 영속화(저장, 유지)하는 목적이 있는 기술입니다. 하지만 실제로 데이터를 영속화하는 작업보다 영속화된 데이터를 조건에 맞게 조회하는 작업이 더 많이 일어나게 됩니다. 현재 포스팅을 보시는 것과 같이 글, 댓글을 작성하는 작업보다 게시글을 조회하시는 일이 훨씬 많은 것을 알 수 있습니다. 이런 식으로 데이터베이스에서는 조회가 빈번하게 일어나고 있습니다. 조건에 맞는 데이터를 조회하기 위해서 테이블에 있는 데이터를 하나하나 확인하는 작업은 성능이 매우 떨어집니다. 인덱스(index)는 컬럼의 값과 레코드가 저장된 주소를 key-value 형태로 만들어 더욱 빠르게 조회할 수 있게 도와줍니다.

 

🟩 B-Tree (Balanaced Tree)

인덱스 구조로 가장 많이 사용하는 자료구조는 B-Tree 입니다. B-Tree는 Balanced Tree로 균형 잡힌 트리입니다. 이진 트리를 생각하셨을 때 한 쪽에 노드가 몰릴 경우에 시간복잡도가 최악의 경우 O(N)이 나올 수 있습니다. 이렇게 편향된 데이터를 가지게 된다면 검색 성능이 안좋아질 수 있습니다. 그리고 이를 해결하기 위해서 균형 잡힌 트리인 B-Tree를 사용합니다. B-Tree의 경우 모든 리프 노드의 레벨이 같기 때문에 O(logN) 시간으로 검색할 수 있습니다.

추가적으로 AVL 트리를 이용해도 O(logN)의 시간으로 조회, 저장, 삭제가 가능하지만 데이터베이스에서는 B-Tree 방식을 선택했습니다. 이유는 secondary storage에서 블록(block) 단위로 가져온 데이터를 더 효율적으로 사용할 수 있으며, 한 노드의 여러 개의 데이터를 가지고 있어 secondary storage를 직접 접근하여 조회해야하는 횟수 자체도 적기 때문입니다.

 

🟩 B-Tree 인덱스 구조

B-Tree는 트리 구조로 이루어져 있습니다. 최상위 단 하나의 루트 노드가 존재하고 그 하위에 브랜치 노드가 존재합니다. 그리고 마지막으로 브랜치 노드의 하위에는 리프 노드가 있습니다. 데이터베이스에서는 인덱스와 실제 데이터는 따로 관리되고 있으며 인덱스의 리프 노드에는 항상 실제 데이터 레코드를 찾아갈 수 있는 주소값을 가지고 있습니다.

 

MySQL에서 사용하는 InnoDB 스토리지 엔진을 기준으로 인덱스는 페이지(page) 단위로 저장되며, 인덱스 키 값을 기준으로 정렬되어 있는 상태입니다.

 

🟧 페이지 (Page)

B-Tree 인덱스 구조를 봤을 때 리프 노드 부분을 더 정확하게 보이면 위와 같이 리프 노드에 여러 페이지가 존재하는 형태입니다. 페이지란 디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 최소 작업 단위를 의미합니다. 일반적인 인덱스를 포함해 프라이머리 키 인덱스와 테이블 등은 모두 페이지 단위로 관리됩니다. 만약 쿼리를 통해 1개의 레코드를 읽고 싶더라도 결국 하나의 블록을 읽어야 합니다.

 

 

🟩 B-Tree 인덱스 조회

데이터베이스에서 인덱스는 보통 아래와 같이 세컨더리 인덱스를 통해서 PK 값을 찾은 후에 프라이머리 키 인덱스를 통해서 원하는 레코드를 찾게됩니다.
post 테이블은 아래와 같은 구조라고 했을 때 세컨더리 인덱스의 리프 페이지에는 인덱스 키, PK가 있지만 이와 다르게 프라이머리 키 인덱스의 리프 페이지에는 실제 레코드가 존재하는 것을 볼 수 있습니다.

CREATE TABLE post (
    id BIGINT NOT NULL PRIMARY KEY AUTO_INCREMENT,
    title VARCHAR(255) UNIQUE
) ENGINE=InnoDB;

세컨더리 인덱스와 프라이머리 키 인덱스가 데이터베이스에서 존재하는 이유는 효율성으로 검색 속도를 최적화하기 위해서입니다. InnoDB에서의 페이지 크기는 보통 16KB 입니다. 세컨더리 인덱스의 리프 페이지를 보면 인덱스 키, PK 의 값이 있지만 프라이머리 키의 인덱스에는 PK와 그에 관련한 데이터의 값이 있습니다. 프라이머리 키 인덱스의 리프 페이지의 각 레코드의 크기가 세컨더리 인덱스의 리프 페이지의 각 로우보다 데이터의 크기가 큽니다. 이러한 이유로 프라이머리 키 인덱스의 리프 페이지의 로우 수가 더 적다고 볼 수 있습니다. 페이지에 있을 수 있는 로우 수가 적다면 그만큼 디스크 I/O 횟수가 증가할 가능성이 있어 비효율적일 수 있습니다. 이러한 이유로 세컨더리 인덱스의 리프 페이지에서는 실제 데이터가 아닌 인덱스 키와 PK를 갖는 로우를 더 많이 가질 수 있도록 하여 디스크 I/O 횟수를 줄이는 방식을 선택했습니다.

 

🟧 세컨더리 인덱스와 프라이머리 키 인덱스

InnoDB의 모든 테이블은 기본적으로 프라이머리 키(PK)를 기준으로 클러스터링되어 저장하고 이를 프라이머리 키 인덱스라고 합니다. 프라이머리 키 인덱스는 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스를 의미합니다. 프라이머리 키 인덱스를 제외한 나머지 모든 인덱스는 세컨더리 인덱스로 분류합니다. 세컨더리 인덱스는 데이터베이스 테이블에서 프라이머리 키(PK) 이외의 컬럼에 대한 추가적인 인덱스를 의미합니다. 프라이머리 키를 기반으로 하는 프라이머리 키 인덱스와는 달리, 세컨더리 인덱스는 테이블 내의 다른 컬럼을 기준으로 데이터를 정렬하고 있습니다.

 

🟩 B-Tree 인덱스 추가

B-Tree에 새로운 키 값이 추가할 때 먼저 적절한 위치를 찾습니다. 저장할 위치를 찾아 추가하게 됐을 때 노드의 개수가 꽉 찻을 경우 노드를 분리하는 작업이 추가적으로 필요해집니다. 테이블에 레코드를 추가하는 작업비용을 1이라고 했을 때 테이블의 인덱스에 키를 추가하는 작업 비용을 1.5 정도로 예측할 수 있습니다. 하지만 실제로 이러한 비용은 메모리와 CPU에서 처리하는데 걸리는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야하기 때문입니다.

InnoDB 스토리지 엔진은 이러한 작업 비용을 줄이기 위해서, 필요하다면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수도 있습니다. 하지만 프라이머리 키, 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 B-Tree에 즉시 추가, 삭제해야 한다. 이러한 작업을 체인지 버퍼가 해주고 있습니다.

 

🟧 체인지 버퍼

InnoDB에서 변경해야 할 인덱스 페이지가 버퍼 풀에 있는 경우에는 디스크 I/O 없이 곧바로 업데이트 할 수 있습니다. 하지만 버퍼 풀에 변경해야 할 인덱스 페이지가 없을 경우 디스크로부터 인덱스 페이지를 읽어와야 합니다. 그래서 디스크로부터 읽어와서 업데이트를 해야할 경우에는 이를 바로 실행하지 않고 임시 공간에 저장해두고 사용자에게 원하는 결과를 반환하여 성능을 향상시킵니다. 여기서 임시 메모리 공간을 체인지 버퍼라고 합니다.

 

🟩 B-Tree 인덱스 삭제

B-Tree 키를 삭제하는 경우에는 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마크만 하면 작업이 완료됩니다. 삭제된 마킹 인덱스를 방치하거나 재활용할 수도 있습니다. 인덱스 키 삭제도 마킹 작업, 디스크 쓰기와 같은 디스크 I/O 작업이 필요합니다. InnoDB 스토리지 엔진에서는 이러한 작업도 지연시켜 나중에 처리할 수 있습니다.

 

🟩 B-Tree 인덱스 수정

인덱스는 키 값에 따라 저장될 리프 노드의 위치가 정해집니다. 때문에 단순히 인덱스 상의 키 값만 변경할 경우 B-Tree에 문제가 생길 수 있습니다. 이를 해결하기 위해서 인덱스 키 값을 삭제한 후 새로운 인덱스 키 값을 추가하는 방식으로 작업을 처리합니다. 수정도 체인지 버퍼를 활용하여 지연 처리를 할 수 있습니다.