[MySQL] B+Tree Index 구조와 Clustered Index에 대한 고찰

사전 개념

• MySQL은 스토리지 엔진으로 InnoDB를 기본값으로 활용한다.
• MySQL은 인덱스 자료구조로 B+Tree를 활용한다.

---

MySQL은 인덱스 자료구조로 B+Tree를 활용한다?

MySQL 공식 문서를 살펴보면 

With the exception of spatial indexes, InnoDB indexes are B-tree data structures.
...
Index records are stored in the leaf pages of their B-tree or R-tree data structure. 

 

라고 나와 있다. 처음엔 알고 있던 것과 다르게 B-tree라길래 깜짝 놀랐는데 자세히 읽어보니 B-tree 리프 페이지들에 저장되는 레코드라고 나와 있어서 B+tree 자체가 리프노드에 값을 저장하는 B-tree이니까 B+tree가 맞구나! 라고 결론을 내렸다.

 

다만 정확히 말하자면 MySQL이 B+Tree를 Index의 자료구조로 활용한다기 보단 InnoDB에서 사용한다는 표현이 정확할 것 같다.

 

InnoDB의 Clustered Index

MySQL의 스토리지 엔진으로는 InnoDB가 대표적이다. 그래서 InnoDB의 특성에 대해 조금 더 알아보고자 한다.

우리가 DB에서 Table을 생성할 때, 보통 Primary Key를 지정해주곤 한다. 이 때, Auto Increment 속성을 부여한 id값을 인조키로 부여해 관리를 하는데 Auto Increment는 값이 UNIQUE함과 NOT NULL을 보장해줌과 동시에 순차적으로 증가하는 값을 할당해주기 때문에 Primary Key로 사용하는데 손색이 없다.

 

InnoDB는 Primary Key를 결정하는 3가지 단계를 거친다.

- When you define a PRIMARY KEY on a table, InnoDB uses it as the clustered index. A primary key should be defined for each table. If there is no logical unique and non-null column or set of columns to use a the primary key, add an auto-increment column. Auto-increment column values are unique and are added automatically as new rows are inserted.

첫번째는 사용자가 Primary Key를 명시한 경우이다. 이 경우 해당 key값을 Primary Key로 설정하고 마무리한다.

- If you do not define a PRIMARY KEY for a table, InnoDB uses the first UNIQUE index with all key columns defined as NOT NULL as the clustered index.

두번째는 사용자가 명시적으로 설정하지 않은 경우이다. 이 경우 값중에 null이 없는 첫번째 Unique Index를 Primary Key로 설정한다.

- If a table has no PRIMARY KEY or suitable UNIQUE index, InnoDB generates a hidden clustered index named GEN_CLUST_INDEX on a synthetic column that contains row ID values. The rows are ordered by the row ID that InnoDB assigns. The row ID is a 6-byte field that increases monotonically as new rows are inserted. Thus, the rows ordered by the row ID are physically in order of insertion.

마지막으로 적합한 Unique Index 또한 없는 경우, InnoDB는 GEN_CLUST_INDEX라는 이름을 가지는 clustered index를 생성해 이를 Primary Key로 사용한다.

 

InnoDB에서 Clustered Index라 함은 Primary Key와 동의어이다. 따라서 Clustered Index를 통해 테이블의 레코드를 조회할 수 있게 된다. 기본적으로 설정되는 Index이기에 조회 작업에는 Primary Key를 통해 조회하는 것이 다른 값들을 통해서 조회하는 것보다 Disk I/O 작업을 줄이고 빠른 성능을 보일 수 있다. 또한 Clustered Index는 조회 시 바로 레코드 데이터가 저장되어 있는 페이지로 접근할 수 있기 때문에 더 좋은 성능을 낸다.

 

그렇다면 Secondary Index로 설정한 경우 Clustered Index보다 낮은 성능을 낸다는 소리인가?

그렇다. Secondary Index는 Primary Key값 즉, Clustered Index를 값으로 가진다. 따라서 InnoDB는 Secondary Index를 통해 Clustered Index를 찾은 후 다시 Clustered Index를 통해 해당 레코드를 찾는 과정을 수행하게 된다. 한층 더 거쳐서 가게 되니까 당연히 Clustered Index를 통해 조회하는 방식이 더 좋은 성능을 낼 수 있다.

 

특정 컬럼으로 조회하는 로직이 많은 경우

그럼 만약에 날짜와 같이 특정 컬럼을 통해서 조회하는 로직이 많은 테이블이라면?

복합키를 사용하자!

https://purumae.tistory.com/209

[MySQL] 사용자 로그 테이블 - (1) Primary Key가 필요한가?

위 글을 보면 로그 데이터를 저장하는 테이블은 날짜로 조회하는 경우가 많다. 그렇기에 날짜를 Primary Key로 설정할 수 있다면 보다 좋은 성능으로 데이터를 조회할 수 있을 것이다. 하지만 날짜는 중복되는 경우가 다반사이기에 날짜 컬럼만으로는 Primary Key의 조건을 만족시킬 수 없다. 따라서 auto increment 속성을 부여한 id값을 함께 복합키로 설정해야 한다.

 

여기서 문제는 날짜 컬럼을 clustered Index로 활용하기 위해서는 복합키의 첫번째 컬럼으로 두어야 한다는 것이다.

다음과 같이 쿼리문을 작성한다.

CREATE TABLE daily_log (
    log_date datetime(0) NOT NULL,
    log_id bigint UNSIGNED NOT NULL AUTO_INCREMENT,
    log_content json NOT NULL,
    PRIMARY KEY (log_date, log_id)
) ENGINE=InnoDB;

 

하지만 이렇게 생성하게 되면 Incorrect table definition; there can be only one auto column and it must be defined as a key에러가 발생하게 된다. 이를 해결하기 위한 방법으로 위 블로그 글에서는 log_id를 secondary index로 두는 방법을 제시했다. 굳이 Clustered Index가 될 필요는 없나보다.

CREATE TABLE daily_log (
    log_date datetime(0) NOT NULL,
    log_id bigint UNSIGNED NOT NULL AUTO_INCREMENT,
    log_content json NOT NULL,
    PRIMARY KEY (log_date, log_id),
    INDEX `nix-daily_log-log_id` (log_id)
) ENGINE=InnoDB;

이렇게 하면 잘 동작한다!

 

다음과 같이 데이터를 넣었다고 가정해보자

insert into daily_log(log_date)
value (CURRENT_DATE), (CURRENT_DATE+1), (CURRENT_DATE+2), 
(CURRENT_DATE+3), (CURRENT_DATE+4), (CURRENT_DATE+5);

 

이때, log_date를 통해서 범위 조회를 한다면

explain select * from daily_log where log_date between current_date-1 and current_date+5;

 

log_date를 통해서 범위 조회

다음과 같이 PRIMARY KEY가 index가 되어서 조회를 하는 것을 알 수 있다. 우리가 의도한대로 Clustered Index를 활용해서 빠르게 조회하는 방식으로 동작한다.

 

하지만 log_id를 통해 조회한다면?

explain select * from daily_log where log_id between 1 and 3;

log_id를 통해 범위 조회

index를 활용하긴 하지만 설정해준 Secondary Index를 통해 조회를 하는 것을 볼 수 있다. Clustered Index는 Primary Key를 복합키로 설정한 경우 첫번째 Column을 통해서만 동작한다고 짐작할 수 있었다.

 

하지만 이렇게 설정하는 것의 문제점은 primary key와 secondary key의 크기가 기존에 비해 커진다는 것이다.

• Primary Key : 5byte(log_date) + 8byte(log_id) = 13 byte 로 기존 8byte에 비해 증가했다.
• Secondary Key : 8byte(log_id) + 13byte(Primary Key) 로 없어도 되는 공간을 13byte나 잡아먹게 되었다.

 

Secondary Key는 key에 해당하는 값을 Primary Key 즉, Clustered Index의 키값을 가지고 있기 때문에 Primary Key가 커지면 Secondary Key가 차지하는 크기도 더 커지게 되어서 문제가 있다.

 

어쩔 수 없이 성능을 얻으면 공간을 낭비해야 하는 트레이드 오프가 있나보다,,,

 

그렇다면 만약에 log_id를 첫번째 컬럼으로 둔다면?

이렇게 된다면 Secondary Key는 굳이 둘 필요가 없기에 낭비하는 공간을 줄일 수 있게될텐데... 결론부터 말하자면 실패!

CREATE TABLE daily_log (
    log_date datetime(0) NOT NULL,
    log_id bigint UNSIGNED NOT NULL AUTO_INCREMENT,
    log_content json null,
    PRIMARY KEY (log_id, log_date),
) ENGINE=InnoDB;

 

1. log_date로 범위 조회를 하는 경우

log_date로 범위 조회

log_date를 secondary index로 설정하지 않았기 때문에 index를 활용하지 못했다. type이 ALL인 것을 보면 알 수 있듯이 Full Scan을 해서 조회를 하게 된다.

 

2. log_id로 범위 조회를 하는 경우

log_id를 통해 범위 조회

이번엔 log_id가 Clustered Index를 통해서 범위 조회를 수행한 것을 볼 수 있다. 

---

결론

이로써 복합키를 Primary Key로 설정한 경우 첫번째 컬럼을 기준으로 조회를 할 경우에만 Clustered Index를 활용할 수 있다는 것을 알게 되었다. 여태까지 단순히 Primary Key로 Auto increment 속성을 부여한 id 인조키 값으로 활용해왔다. 이제는 사용하는 테이블의 특성에 따라 Primary Key도 조회 성능을 높이는 방향으로 설정하는 것도 고려해봐야겠다.

 

참고 사이트

https://dev.mysql.com/doc/refman/8.3/en/innodb-physical-structure.html

MySQL :: MySQL 8.3 Reference Manual :: 17.6.2.2 The Physical Structure of an InnoDB Index