인덱스 내부 작동
MySQL에서 인덱스는 내부적으로 균형 트리의 형태로 구성되며 일반적으로 B-Tree 자료 구조를 사용한다. B-Tree란 데이터를 정렬된 상태로 저장하며 효율적인 검색, 삽입, 삭제를 지원하는 균형 이진 트리(Balanced Tree)의 종류이다.
균형 트리의 개념
균형 트리에 대해 이해하기 위해서는 노드(node)에 대한 이해가 필요하다. 노드(node)란 균형 트리 구조에서 데이터가 저장되는 공간이다. 위 그림에는 4개의 노드가 존재한다.
루트 노드(root node)는 노드의 가장 상위 노드로 모든 출발은 루트 노드에서 시작한다. 리프 노드(leaf node)는 제일 마지막에 존재하는 노드이며, 중간 노드(internal node)는 루트 노드와 리프 노드의 중간에 존재하는 노드이다.
MySQL에서 노드는 페이지(Page)라 불리는데 페이지는 최소한의 저장 단위로 16Kbyte(16384byte)가 사용된다. 데이터를 1건만 입력해도 1개의 페이지(16Kbyte) 필요하다.(노트에 1개의 단어만 적고 싶어도 1장이 필요한 것과 마찬가지로 1건의 데이터만 입력해도 1페이지가 필요하다.)
만약 데이터베이스의 데이터가 위 그림처럼 구성되어있는 상태에서 MMM이라는 데이터를 검색하면 모두 리프 페이지만 존재하므로 AAA부터 MMM까지 총 8건의 데이터를 검색해야 한다. 즉 처음부터 검색하는 방법을 사용하게 되고, 이는 전체 테이블 검색(Full Table Scan)이라고 한다.
전체 테이블 검색(Full Table Scan)이란 데이터를 처음부터 끝까지 검색하는 것을 말한다.
균형 트리는 무조건 루트 페이지부터 검색하며, 모든 데이터는 정렬된 상태이다.
여기서도 MMM을 검색한다고 가정해보자. MMM은 AAA, FFF, LLL 3개를 읽은 다음 사전상 LLL 뒤에 나오는 단어이므로 LLL과 연결된 세 번째 리프 페이지로 이동한다. 그리고 LLL, MMM을 읽어서 MMM을 찾게되고 AAA → FFF → LLL(루트 페이지) →LLL(리프 페이지) → MMM의 순으로 읽게 되어 총 5건의 데이터를 검색하게 된다.
균형 트리가 아닐 때는 3개의 페이지를 읽었으나 균형 트리일 때는 2개의 페이지를 읽게 되면서 더 효율적인 검색이 가능해졌다. 참고로 읽은 데이터의 건수가 중요한 것이 아니라 읽은 페이지의 수로 효율성을 판단할 수 있다. 따라서 균형 트리를 구성하면 데이터를 빠르게 검색할 수 있다.
균형 트리의 페이지 분할
인덱스는 균형 트리로 구성되어 있어서 SELECT 속도가 향상될 수 있다.(더 적은 수의 페이지를 읽으므로) 하지만 인덱스를 구성하면 데이터 변경 작업의(INSERT, UPDATE, DELETE) 성능이 저하되는데, 특히 INSERT 작업이 일어날 때 페이지 분할 작업이 발생할 수 있기에 더 느리게 데이터가 더 느리게 삽입될 가능성이 높아진다.
페이지 분할이란 새로운 페이지를 준비해서 데이터를 나누는 작업을 말하는데, 페이지 분할이 발생하면 MySQL이 느려지고 자주 일어나면 성능이 저하된다. 구체적으로 왜 인덱스를 구성하면 데이터 변경 작업이 느려지는지 알아보도록 하자.
데이터 삽입 상황을 가정하기 위해 위 균형 트리의 상황에서 III 데이터를 삽입한다고 가정해보자.
III가 새롭게 INSERT되는 경우 2가지의 작업이 발생한다.
- III가 순서상 두번째 리프 페이지에 삽입되기 위해 JJJ가 한 칸 이동한다.
- JJJ가 이동 후 남게 된 빈칸에 III가 삽입된다.
이 작업은 JJJ가 한 칸 이동했을 뿐 아직 큰 변화는 없다. 성능 상으로도 큰 문제는 없을 것이다.
이번에는 GGG 데이터를 삽입하도록 해보자.
GGG 데이터는 순서상 두번째 리프 페이지에 들어가야 한다. 하지만 현재 두번째 리프 페이지는 데이터로 꽉 찬 상태이다. 따라서 페이지 분할 작업이 발생하는데, 이 과정에서 새 페이지가 확보되고 페이지 분할 작업이 1회 발생한다.
또한 리프 페이지가 분할됨에 따라 루트 페이지에 반영되어야 하기에 루트 페이지에 새로 등록된 페이지의 최상위 데이터가 등록된다.
이번에는 PPP 데이터를 삽입하도록 해보자.
PPP를 삽입 시 순서 상에 따라 네 번째 리프 페이지 빈 공간에 삽입된다. 해당 작업은 별도의 페이지 분할 작업이 발생하지 않았기에 성능상 큰 문제를 일으키진 않을 것이다. 이번에는 QQQ 데이터를 삽입하도록 해보자.
QQQ 데이터는 순서 상 마지막 리프 페이지에 삽입되어야 하나 마지막 리프 페이지에 빈 공간이 없으므로 새 페이지가 생성되고 페이지 분할 작업이 발생한다. 리프 페이지가 추가 되었으므로 루트 페이지에 해당 데이터를 등록해야 한다.
그러나 이미 루트 페이지도 빈 공간이 없는 상태이므로, 리프 페이지의 데이터를 반영하기 위해 2개의 중간 페이지로 분할된다. 그리고 2개의 중간 페이지의 정보를 담은 루트 페이지를 새롭게 생성하게 된다.
따라서 균형 트리의 최종적인 모습은 위와 같고, QQQ 하나를 입력하기 위해 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;<결과>
현재 cluster 테이블을 생성했으며 기본 키를 지정하지 않았기 때문에 따로 인덱스가 없는 상태이며 정렬된 순서는 입력된 순서와 동일하다.
따라서 현재 데이터 페이지의 상태는 위와 같다고 할 수 있다. 페이지의 위에 있는 1000, 1001, 1002는 페이지 번호로 실제로 위와 같이 페이지 번호가 매겨지지는 않는다.
그렇다면 만약 클러스터형 인덱스를 생성한다면 데이터 페이지는 어떻게 변경될까?
<실행>
ALTER TABLE cluster ADD CONSTRAINT PRIMARY KEY(mem_id);
SELECT * FROM cluster;<결과>
mem_id에 클러스터형 인덱스 구성 후 데이터를 확인하면 mem_id를 기준으로 오름차순 정렬되는 것을 확인할 수 있다. 앞서 인덱스 (1)에서 언급했듯이 클러스터형 인덱스를 생성하면 데이터가 자동 정렬된다.
그렇다면 클러스터형 인덱스를 생성하면 페이지는 어떤식으로 변할까?
실제로 데이터 페이지가 정렬되고 균형 트리 형태의 인덱스가 형성된다. 행 데이터를 클러스터형 인덱스로 지정한 열로 정렬하고, 각 페이지의 인덱스로 지정된 열의 첫 번째 값을 가지고 루트 페이지를 형성한다.
클러스터형 인덱스는 루트 페이지와 리프 페이지로 구성되며 인덱스 페이지의 리프 페이지는 데이터 그 자체가 된다. 즉 리프 페이지 = 데이터 페이지라고 할 수 있다.
보조 인덱스 구성하기
앞서 자동 정렬되는 클러스터형 인덱스를 생성하고, 페이지의 구조를 살펴보았다. 이번에는 보조 인덱스를 살펴보도록 하자.
<실행>
USE market_db;
DROP TABLE IF EXISTS second;
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', '마마무');
ALTER TABLE second ADD CONSTRAINT UNIQUE(mem_id);
SELECT * FROM second;<결과>
고유 키 제약 조건으로 보조 인덱스를 생성했다. 보조 인덱스는 생성하여도 결과는 입력한 것과 동일한 순서로 출력되며, 이는 자동 정렬이 되지 않는다는 것을 의미한다.
인덱스의 구조는 위와 같은데, 보조 인덱스는 데이터 페이지를 따로 건드리지 않는다. 즉 별도의 장소에 인덱스 페이지를 생성하여 데이터를 조회하는데, 인덱스 페이지의 리프 페이지에 인덱스로 구성한 열을 정렬한다. 그리고 그 값으로 실제 데이터의 위치를 준비하는데, 데이터의 위치는 페이지 번호 +#오프셋으로 위치를 기록한다.
인덱스 유형별 데이터 검색
인덱스 유형별로 데이터가 어떻게 검색되는 알아보도록 하자.
클러스터형 인덱스
클러스터형 인덱스가 구성된 테이블에서 ID가 SPC인 회원의 이름을 검색하려면 루트 페이지를 읽고 리프 페이지를 읽으면 되므로 2개 페이지를 읽어서 SPC의 이름을 확인할 수 있다.
보조 인덱스
보조 인덱스가 구성된 테이블에서 ID가 SPC인 회원의 이름을 검색하려면 루트 페이지를 읽고 리프 페이지를 읽은 뒤, 실제 데이터 페이지를 읽으면 되므로 3개 페이지를 읽어서 SPC의 이름을 확인할 수 있다.
인덱스 검색(Index Scan)을 통해 클러스터형은 2페이지를, 보조 인덱스는 3페이지를 읽어서 원하는 결과를 검색할 수 있다. 비교 결과 클러스터형 인덱스가 보조 인덱스보다 검색이 조금 더 빠른 것을 알 수 있다.
출처
- 혼자 공부하는 SQL(우재남 저, 한빛미디어)
