[혼공S] CH6-(2). 인덱스의 내부 작동

클러스터형 인덱스와 보조 인덱스느 모두 내부적으로 균형 트리로 만들어진다. 여기서 균형 트리(Balanced tree, B-tree)는 자료구조에서 사용되는 데이터의 구조로, 뿌리, 줄기, 잎으로 구성되어 있다. 

 

인덱스의 내부 작동 원리

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

 

균형 트리의 개념

균형 트리 구조에서 데이터가 저장되는 공간을 노드(node)라고 한다. 루트 노드(root node)는 가장 상위의 노드를 말하고, 모든 출발은 루트노트에서 시작되고 리프노트(leaf node)로 마무리된다. 이 사이에 있는 노드는 중간 노드(internal node)라고 부른다. MySQL에서는 node 대신 페이지(page)라고 부른다. 

 

균형 트리의 페이지 분할

균형 트리를 이용하면 데이터를 검색하는 데 더 효율적이다. 인덱스는 균형 트리로 구성되어 있다. 즉, 인덱스를 만들면 SELECT의 속도를 향상시킬 수 있는데, 이는 데이터 변경 작업 시에는 효율적이지 않게 된다. 즉, INSERT, UPDATE, DELETE 시에는 '페이지 분할'이라는 작업 때문에 더 느려질 수 있다. 

 

인덱스의 구조

인덱스 구조를 통해 데이터가 왜 정렬되는지 알아보고, 어떤 인덱스가 더 효율적인지 알아보고자 한다.

 

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

먼저 PRIMARY KEY 없이 cluster라는 테이블을 생성해본다.

USE market_db ;
DROP TABLE IF EXISTS cluster ; 
-- cluster 테이블 생성
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('WNN', '여자친구') ;
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('MMW', '마마무') ;
SELECT * FROM cluster ;

입력한 순서대로 테이블이 구성된 것을 볼 수 있다. 이후에 PRIMARY KEY를 지정한 후 테이블을 출력해본다. 

-- 클러스터형 인덱스 구성하기 
ALTER TABLE cluster 
   ADD CONSTRAINT 
   PRIMARY KEY (mem_id) ; 
SHOW INDEX FROM cluster ;
SELECT * FROM cluster ;

PRIMARY KEY를 설정을 하면 클러스터형 인덱스가 생성이 되고 위와 같이 데이터가 해당 열을 기준으로 정렬된다. 그리고 실제 데이터는 데이터 페이지가 정렬되고 균형 트리 형태의 인덱스가 형성이 된다. 그리고 각 페이지의 인덱스로 지정된 첫 번째 값을 가지고 루트페이지를 만들게 된다. 

 

보조 인덱스 구성하기

동일한 데이터로 보조 인덱스를 만들어보자. 보조 인덱스는 UNIQUE 문으로 지정하면 만들어진다.

-- 똑같은 테이블 만들기
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('MMW', '마마무') ; 
SELECT * FROM second ;
-- 보조 인덱스 생성
ALTER TABLE second 
   ADD CONSTRAINT
   UNIQUE (mem_id) ; 
SELECT * FROM second ;

보조 인덱스가 생성되면 데이터의 입력 순서는 바뀌지 않는다. 보조 인덱스는 책의 맨 뒤에 있는 찾아보기와 같다고 보면 된다. 즉, 인덱스 페이지의 리프 페이지에 인덱스로 구성한 열(mem_id)을 정렬한다. 그 뒤에 실제 데이터가 있는 위치를 준비한다. 데이터의 위치는 페이지번호 + #위치 형식처럼 기록될 수 있다. (p.302에서 그림으로 자세히 설명되어 있음.) 

 

Reference

혼자 공부하는 SQL, 우재남 지음