[혼자공부하는SQL] 16강

06-2. 인덱스의 내부 작동

0. 시작하기 전에

• 클러스터형 인덱스와 보조 인덱스는 모두 내부적으로 ‘균형 트리’로 만들어진다.

1) 균형 트리란?

: 균형 트리(Balanced tree, B-tree)는 ‘자료 구조’에 나오는 범용적으로 사용되는 데이터 구조이다.

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

1. 인덱스의 내부 작동 원리

• 인덱스의 내부 작동 원리를 이해하면, 인덱스를 사용해야 할 경우와 사용하지 말아야 할 경우를 선택할 때 도움이 된다.
• 인덱스가 늘 좋은 것은 아니므로, 정확히 판단하는 것이 중요하다.

1) 균형 트리의 개념

• 균형 트리에서 데이터가 저장되는 공간을 노드(Node)라고 한다.

(1) 용어 정리

• 루트 노드(root node) : 노드의 가장 상위 노드
  • 모든 출발은 루트 노드에서 시작된다.
• 리프 노드(leaf node) : 제일 마지막에 존재하는 노드
  • 데이터가 많다면 3단계나 그 이상이 될 수 있다.
• 중간 노드(internal node) : 루트 노드와 리프 노드의 중간에 끼인 노드들
• 페이지(page) : 노드라는 용어는 개념적인 설명에서 주로 나오는 용어이며, MySQL에서는 페이지라고 부른다.

(2) 전체 테이블 검색(Full Table Scan)로 진행한 경우

• 의미 : 데이터를 처음부터 끝까지 검색하는 것
• 예시 : 인덱스가 없는 상황 (모두 리프 페이지만 있는 경우)
• 페이지를 몇 개이나 넘겼는지가 더 중요하다. (위의 예시에서는 3개의 페이지)

(3) 균형 테이블로 진행한 경우

• 무조건 루트 페이지부터 검색한다.
• 루트 페이지를 추가한다. (새로운 값이 아닌, 기존의 각 리프 페이지의 가장 위에 있는 것들만 가져온다.)
• 균형 테이블을 한경우 2개의 페이지만 읽어서 결과를 얻는다.
• LLL 다음에 있을 것이기에, AAA와 FFF는 생략한다.
• 인덱스가 있든 없든 결과가 바뀌는 것은 아니지만, 속도의 차이가 있다.

2) 균형 트리의 페이지 분할

• 인덱스를 구성하면 SELECT의 속도는 빨라질 수 있다.
• 하지만, 데이터 변경 작업(INSERT, UPDATE, DELETE) 시 성능이 나빠진다.
  • 특히 INSERT 작업이 일어날 때 더 느리게 입력될 수 있다.
  • 이유 : 페이지 분할이라는 작업이 발생해서

(1) 페이지 분할

: 새로운 페이지를 준비해서 데이터를 나누는 작업

• 페이지 분할이 일어나면, MySQL이 느려지고, 너무 자주 일어나면 성능에 큰 영향을 준다.

(2) 예시

• 상황1 : III 데이터를 INSERT한 경우
  • 두 번째 리프 페이지에는 빈 공간이 있어서 JJJ가 아래로 한 칸 내려가고, III가 그 자리에 삽입되었다.
  • 정렬되어야 하기 때문에 JJJ가 한 칸 이동했을 뿐 큰 변화는 일어나지 않는다.
  • 즉 III를 입력하는 작업은 순식간에 처리가 된다.

• 상황2 : GGG 데이터를 INSERT한 경우
  • 해당 페이지에서 더 이상 내릴 수 있는 공간이 없다.
  • 따라서 두 번째 리프 페이지에서 새 페이지를 준비하고, 데이터를 적당히 나눈다.
  • 즉, 페이지 분할이 한 번 일어나게 되었다.
• 이렇게 진행하면 느려지게 된다.

• 상황3 : PPP 데이터를 INSERT한 경우
  • 페이지 분할이 일어난다.
  • LLL과 PPP의 헤드가 루트 페이지로 올라가야 하는데, 공간이 없다.
  • 루트 페이지도 페이지 분할이 일어난다.
  • 루트 페이지는 한 페이지가 되어야 하므로, 기존의 루트 페이지는 중간 페이지가 되고, 새로운 루트 페이지가 만들어진다.
• 이렇게 진행하면, 이전 상황보다 더 많이 느려지게 된다.

2. 인덱스의 구조

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

(1) 데이터 페이지 구성하기

• 아직 인덱스가 없는 상황

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', '마마무');

(2) 클러스터형 인덱스 지정하기

ALTER TABLE cluster
    ADD CONSTRAINT
    PRIMARY KEy (mem_id);

SELECT * FROM cluster;

• mem_id에 PK를 지정함으로써, 오름차순 정렬된 결과를 보여준다.

• 사진과 같이 정리가 된다.
• 루트페이지가 만들어지고, 리프 페이지로 구분된다.

2) 보조 인덱스 구성하기

(1) 데이터 페이지 구성하기

• 아직 인덱스가 없는 상황

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', '마마무');

(2) 보조 인덱스 지정하기

ALTER TABLE second
    ADD CONSTRAINT 
    UNIQUE (mem_id);

SELECT * FROM second;

• 데이터 결과가 바뀌지는 않았지만, 각각의 위치(인덱스)가 추가가 된 상태이다.
• 사진과 같이 정리가 된다.
• 루트페이지가 만들어지고, 리프 페이지로 구분된다.

3) 인덱스에서 데이터 검색하기

: 이제 데이터를 검색해보고, 어떤 인덱스가 효율적인지 보려고 한다.

• 상황 : SPC 회원의 이름을 알아내고자 한다.

(1) 클러스터형 인덱스에서 데이터 찾기

• 루트 페이지를 읽고 MMU 페이지를 찾는다.
• MMU 페이지를 읽고 SPC를 찾는다.
• SPC의 이름 우주소녀를 검색한다.

(2) 보조 인덱스에서 데이터 찾기

• 루트 페이지를 읽고 OMY 페이지를 찾는다.
• OMY 페이지를 읽고 SPC 페이지를 찾는다.
• SPC 페이지를 읽고 SPC를 찾는다.
• SPC의 이름 우주소녀를 검색한다.

(3) 결론

• 인덱스 검색(Index Scan)을 통해 클러스터형 인덱스는 2페이지만 읽어서 원하는 결과를 검색했고, 보조 인덱스는 3페이지를 읽어서 원하는 결과를 검색했다.
• 두 인덱스 모두 검색이 빠르기는 하지만, 클러스터형 인덱스가 조금 더 빠르다.