Sieun Kim

안녕하세요 :)

3 분 소요

인덱스

인덱스의 내부 작동

클러스터형 인덱스와 보조 인덱스는 모두 내부적으로 균형 트리로 만들어진다.
균형 트리(Balanced tree, B-tree)는 ‘자료 구조’에 나오는 범용적으로 사용되는 데이터의 구조이다.

나무를 거꾸로 표현한 자료 구조로, 트리에서 제일 상단의 뿌리를 루트, 줄기를 중간, 끝에 달린 잎을 리프라고 부른다.

인덱스 내부 작동 원리

인덱스의 내부 작동 원리를 이해하면, 인덱스를 사용해야 할 경우와 사용하지 말아야 할 경우를 선택할 때 도움이 된다.

균형 트리의 개념

균형 트리 구조에서 데이터가 저장되는 공간은 노드(node)라고 한다.

루트 로드(root node)는 노드의 가장 상위 노드를 말한다.
모든 출발은 루트 노드에서 시작된다.
리프 노드(leaf node)는 제일 마지막에 존재하는 노드를 말한다.
루트 노드와 리프 노드의 중간에 끼인 노드들은 중간 노드(internal node)라고 부른다.

노드라는 용어는 개념적인 설명에서 주로 나오는 용어이며, MySQL에서는 페이지(page)라고 부른다.
페이지는 최소한의 저장 단위로, 16Kbyte(16384byte) 크기를 가진다.

균형 트리는 데이터를 검색할 때(SELECT 구문을 사용할 때) 아주 뛰어난 성능을 발휘한다.
만약 리프 페이지만 있을 때, MMM이라는 데이터를 찾으려면 전체 페이지를 검색하는 방법밖에 없다.

균형 트리는 무조건 루트 페이지부터 검색한다.
모든 데이터는 정렬되어 있고 MMM은 루트 페이지를 읽은 다음에 해당 리프 페이지로 직접 이동하면 된다.

위에서 균형 트리가 아닌 구조에서보다 균형 트리에서는 더 적은 페이지를 읽고 결과를 얻을 수 있었다.

균형 트리의 페이지 분할

인덱스를 구성하면 데이터 변경 작업(INSERT, UPDATE, DELETE) 시 성능이 나빠진다.
특히 INSERT 작업이 일어날 때 더 느리게 입력될 수 있다.
이유는 페이지 분할이라는 작업이 발생하기 때문이다.
페이지 분할이란 새로운 페이지를 준비해서 데이터를 나누는 작업을 말한다.
페이지 분할이 일어나면 MySQL이 느려지고, 너무 자주 일어나면 성능에 큰 영향을 준다.

균형 트리에 데이터가 새로 INSERT되었다고 가정해보겠다.

데이터가 정렬되어 삽입될 리프 페이지에 빈 공간이 있을 때는 큰 변화가 일어나지 않는다.

그런데 리프 페이지에 더 이상 빈 공간이 없을 때는 페이지 분할 작업이 일어난다.
우선 새 페이지를 확보한 후 페이지 분할 작업이 1회 일어났고, 루트 페이지에도 새로 등록된 페이지의 제일 위에 있는 데이터가 등록되었다.

데이터가 계속 추가되어 새로운 리프 페이지를 루트 페이지에 등록하려고 하니, 루트 페이지도 이미 꽉 차서 더 이상 등록할 곳이 없다.
그래서 루트 페이지도 다시 페이지 분할을 해야 한다.
그리고 원래 루트 페이지가 있던 곳은 2개의 페이지가 되어 더 이상 루트 페이지가 아니라 중간 페이지가 된다.
마지막으로 새 페이지를 준비해서 중간 노드를 가리키는 새로운 루트 페이지로 구성된다.

결국 하나를 입력하기 위해서 3개의 새로운 페이지가 할당되고 2회의 페이지 분할이 되었다.
이 예를 통해 인덱스를 구성하면 왜 데이터 변경(특히 INSERT) 작업이 느려지는지 확인할 수 있었다.

인덱스의 구조

인덱스 구조를 통해 인덱스를 생성하면 왜 데이터가 정렬되는지, 어떤 인덱스가 더 효율적인지 살펴보겠다.

클러스터형 인덱스 구성하기

우선 인덱스 없이 테이블을 생성하고 다음과 같이 데이터를 입력해보겠다.

USE market_db;
CREATE TABLE cluster
( mem_id    CHAR(8),
  mem_name  VARCHAR(10)
);
INSERT INTO cluster VALUES('TWC', '트와이스');
INSERT INTO cluster VALUES('BLK', '블랙핑크');
INSERT INTO cluster VALUES('WMN', '여자친구');
INSERT INTO cluster VALUES('OMY', '오마이걸');
INSERT INTO cluster VALUES('GRL', '소녀시대');
INSERT INTO cluster VALUES('ITZ', '잇지');
INSERT INTO cluster VALUES('RED', '레드벨벳');
INSERT INTO cluster VALUES('APN', '에이핑크');
INSERT INTO cluster VALUES('SPC', '우주소녀');
INSERT INTO cluster VALUES('MMU', '마마무');

정렬된 순서를 확인해보겠다.

SELECT * FROM cluster;

스크린샷 2024-06-04 181607

-> 입력된 순서와 동일한 순서로 보인다.

이제 테이블의 mem_id에 클러스터형 인덱스를 구성해보겠다.
mem_id를 Primary Key로 지정하면 클러스터형 인덱스로 구성된다.

ALTER TABLE cluster
    ADD CONSTRAINT
    PRIMARY KEY (mem_id);

데이터를 다시 확인해보겠다.

SELECT * FROM cluster;

스크린샷 2024-06-04 182433

-> mem_id를 기준으로 오름차순 정렬되었다.

실제 데이터는 데이터 페이지가 정렬되고 균형 트리 형태의 인덱스가 형성된다.

먼저 클러스터형 인덱스를 구성하기 위해 행 데이터를 지정한 열로 정렬한다.
그리고 각 페이지의 인덱스로 지정된 열의 첫 번째 값을 가지고 루트 페이지를 만든다.

인덱스 페이지의 리프 데이터는 데이터 그 자체이다.

보조 인덱스 구성하기

이번에는 동일한 데이터로 보조 인덱스를 만들어보겠다.

USE market_db;
CREATE TABLE second
( mem_id    CHAR(8),
  mem_name  VARCHAR(10)
);
INSERT INTO second VALUES('TWC', '트와이스');
INSERT INTO second VALUES('BLK', '블랙핑크');
INSERT INTO second VALUES('WMN', '여자친구');
INSERT INTO second VALUES('OMY', '오마이걸');
INSERT INTO second VALUES('GRL', '소녀시대');
INSERT INTO second VALUES('ITZ', '잇지');
INSERT INTO second VALUES('RED', '레드벨벳');
INSERT INTO second VALUES('APN', '에이핑크');
INSERT INTO second VALUES('SPC', '우주소녀');
INSERT INTO second VALUES('MMU', '마마무');

mem_id 열에 UNIQUE를 지정하여 보조 인덱스를 생성하고 데이터를 확인해보겠다.

ALTER TABLE second
    ADD CONSTRAINT
    UNIQUE (mem_id);
SELECT * FROM second;

스크린샷 2024-06-04 182433

-> 보조 인덱스가 생성되었는데도 입력한 것과 순서가 동일하다.

보조 인덱스는 데이터 페이지를 건드리지 않고, 별도의 장소에 인덱스 페이지를 생성한다.

우선 인덱스 페이지의 리프 페이지에 인덱스로 구성한 열(mem_id)을 정렬한다.
그리고 실제 데이터가 있는 위치를 준비한다.
데이터의 위치는 ‘페이지번호 + #위치’로 기록되어 있다.

참고