Database Internals

B-Tree 인덱스의 깊이에 대해서

MySQL 테이블의 B-Tree 인덱스 깊이는 아무리 대용량 테이블이더라도 5단계 이상 깊어지지 않는다. 실제로도 그러할까?
넌 리프 페이지(Non-Leaf Pages)와 리프 페이지(Leaf Pages)의 포맷을 기준으로 이를 간단히 검증해보자.

B-Tree 인덱스는 루트(Root)-브랜치(Branch)-리프(Leaf) 노드로 구성되지만 루트 노드는 B-Tree 크기에 따라서 넌 리프 노드일 수도 있고, 리프 노드일 수도 있다. 때문에 검증은 세 단계 분류(Root, Branch, Leaf)가 아닌 두 단계 분류(Non-Leaf, Leaf)로 진행한다.

InnoDB에는 33개의 페이지 유형이 존재하는데, 그 중 B-Tree 인덱스의 페이지 유형은 B-tree node이다. 넌 리프 페이지와 리프 페이지의 페이지 유형은 B-Tree node로 동일하지만 이 두 페이지는 트리 레벨(tree level)로 세부 유형을 구분할 수 있다. 트리 레벨이 0이면 리프 페이지이며, 1이면 넌 리프 페이지이다.

먼저 아래와 같이 user 테이블을 생성한다.

CREATE TABLE `user` (
  `id` int NOT NULL AUTO_INCREMENT,
  `user_id` int NOT NULL,
  `user_name` char(60) NOT NULL,
  `user_address` char(200) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `ix_userid` (`user_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

그 다음, 데이터를 넣지 않은 상태로 user 테이블이 생성되어 있는 MySQL 데이터 디렉터리로 이동한다. InnoDB 페이지 분석용으로 간단하게 개발한 innodb_page_analyzer로 user.ibd 파일의 페이지 구조를 확인해본다.

출력되는 여러 페이지 유형 중에서 11번째와 12번째 줄에 B-tree node 유형이 존재하는데, 이 중 프라이머리 키 인덱스가 page_num=4에 해당하며, 세컨더리 인덱스(ix_userid)가 page_num=5에 해당한다. 아직 레코드를 삽입하지 않았기 때문에 record_count는 0인 것을 확인할 수 있다.

$ cd /usr/local/mysql/data/
$ innodb_page_analyzer user.ibd

- InnoDB tablespace file: user.ibd
- Pages: 8

page_type = File space header(0x0008)                page_num = 0        page_prev = 90100    page_next = 1        record_count = 0        tree_level = 0        index_id = 18446744069414649855 garbage_space = 0
page_type = Insert buffer bitmap(0x0005)             page_num = 1        page_prev = 0        page_next = 0        record_count = 0        tree_level = 0        index_id = 0                    garbage_space = 0
page_type = Index node(0x0003)                       page_num = 2        page_prev = 0        page_next = 0        record_count = 0        tree_level = 0        index_id = 18446744069414649855 garbage_space = 65535
page_type = Tablespace SDI Index page(0x45bd)        page_num = 3        page_prev = -1       page_next = -1       record_count = 2        tree_level = 0        index_id = 18446744073709551615 garbage_space = 0
page_type = B-tree node(0x45bf)                      page_num = 4        page_prev = -1       page_next = -1       record_count = 0        tree_level = 0        index_id = 165                  garbage_space = 0
page_type = B-tree node(0x45bf)                      page_num = 5        page_prev = -1       page_next = -1       record_count = 0        tree_level = 0        index_id = 166                  garbage_space = 0
page_type = Freshly allocated page(0x0000)           page_num = 0        page_prev = 0        page_next = 0        record_count = 0        tree_level = 0        index_id = 0                    garbage_space = 0

이 상태에서 아래와 같이 user 테이블에 레코드를 삽입하는 프로시저를 작성하고 53건의 데이터를 테이블에 저장한다.

mysql> delimiter ;;

mysql> CREATE PROCEDURE add_user(
     IN count INT
)
BEGIN
  DECLARE i INT;
  SET i = 1;
  WHILE i <= count DO
    insert into user(user_id, user_name, user_address) SELECT 100000%floor(rand()*100000+1), case when floor(rand()*10+1) between 1 and 2 then 'aaaaaaaa' when floor(rand()*10+1) between 3 and 4 then 'bbbbbbbb' when floor(rand()*10+1) between 5 and 6 then 'cccccccc' when floor(rand()*10+1) between 7 and 8 then 'dddddddd' when floor(rand()*10+1) between 9 and 10 then left(uuid(), 8) else 'zzzzzzzz' end, concat('test', left(uuid(), 4));
    SET i = i + 1;
  END WHILE;
  END;;

mysql> delimiter ;
mysql> call add_user(53);
Query OK, 1 row affected (0.01 sec)

그리고 다시 innodb_page_analyzer로 user.ibd 파일의 페이지를 확인해본다(가독성을 위해 B-tree node 유형만 표기하였다).
데이터를 넣지 않았을 때와는 다르게 record_count가 53건 표기되는 것을 확인할 수 있다.

innodb_page_analyzer user.ibd

- InnoDB tablespace file: user.ibd
- Pages: 8

page_type = B-tree node(0x45bf)                      page_num = 4        page_prev = -1       page_next = -1       record_count = 53       tree_level = 0        index_id = 169                  garbage_space = 0
page_type = B-tree node(0x45bf)                      page_num = 5        page_prev = -1       page_next = -1       record_count = 53       tree_level = 0        index_id = 170                  garbage_space = 0

이어서 이번에는 레코드 1건(총 54건)을 추가로 user 테이블에 저장한다.

mysql> call add_user(1);
Query OK, 1 row affected (0.01 sec)

그리고 다시 user.ibd의 페이지 구조를 확인해보면, 위의 페이지 구조와는 다르게 page_num=6과 page_num=7이 새로 생성된 것을 확인할 수 있다. 이는 page_num=4에 해당하는 프라이머리 키 인덱스 페이지가 페이지 분할(실제로 분할되는 것은 아니고 루트 페이지에 대한 포인팅이 변경되고 리프 페이지에 대한 신규 페이지가 생성된다)되었기 때문이다. 출력된 데이터를 좀 더 자세히 보면 6번째줄(page_num=4)의 tree_level은 1이고, 8번째와 9번째줄(page_num=6, 7)의 tree_level은 0인 것을 볼 수 있는데, 앞서 설명했듯이 트리 레벨이 1이면 넌 리프 페이지이고, 트리 레벨이 0이면 리프 페이지이다. 즉 B-tree 인덱스의 깊이가 2가 되기 전에 16KB InnoDB 리프 페이지에 저장될 수 있는 레코드 건 수는 user 테이블의 경우 최대 53건인 것이다.

innodb_page_analyzer user.ibd

- InnoDB tablespace file: user.ibd
- Pages: 9

page_type = B-tree node(0x45bf)                      page_num = 4        page_prev = -1       page_next = -1       record_count = 2        tree_level = 1        index_id = 169                  garbage_space = 0
page_type = B-tree node(0x45bf)                      page_num = 5        page_prev = -1       page_next = -1       record_count = 54       tree_level = 0        index_id = 170                  garbage_space = 0
page_type = B-tree node(0x45bf)                      page_num = 6        page_prev = -1       page_next = 7        record_count = 26       tree_level = 0        index_id = 169                  garbage_space = 7722
page_type = B-tree node(0x45bf)                      page_num = 7        page_prev = 6        page_next = -1       record_count = 28       tree_level = 0        index_id = 169                  garbage_space = 0

또한 넌 리프 페이지는 16KB 페이지에 저장할 수 있는 레코드 건 수가 최대 1226건이다(이 값은 innodb_page_analyzer를 통해 확인해도 되고, 제레미 콜의 블로그에서 인덱스의 레코드 포맷으로 확인해도 된다). 넌 리프 페이지에 1227건이 저장되면 B-tree 인덱스의 깊이가 3이 된다는 말이기도 하다.

그렇다면 B-tree 인덱스 깊이에 따른 테이블 전체 레코드 수는 어떠할까?

깊이 1의 user 테이블 전체 레코드 건 수는 리프 페이지밖에 존재하지 않으므로 최대 53건(16KB)이며, 깊이 2의 user 테이블 전체 레코드 건 수는 ‘넌 리프 페이지의 레코드 건 수 * 리프 페이지당 레코드 건 수’이기 때문에 1226*53 이므로 최대 64,978건(19.1MB)이다. 동일한 방식으로 B-tree 인덱스의 깊이 3은 최대 약 8천만 건(22.9GB)이며, 깊이 4는 최대 약 976억 건(27.4TB)이다. 27TB의 대용량 테이블임에도 B-tree 인덱스의 깊이가 4에서 그치는 것이다.

이번에는 user 테이블의 id 데이터 타입을 INT에서 BIGINT로 변경하면 어떠할까?

id가 BIGINT일 때 리프 페이지에 저장할 수 있는 최대 레코드 건 수는 52건이며, 넌 리프 페이지에 저장할 수 있는 최대 레코드 건 수는 927건이다. 리프 페이지는 INT일 때와 크게 차이가 없지만, 넌 리프 페이지는 최대 레코드 건 수가 많이 줄어든 것을 볼 수 있다. 이는 넌 리프 페이지에 저장 가능한 최대 건 수가 프라이머리 키 사이즈에 가장 큰 영향을 받기 때문이다. 리프 페이지는 user 테이블에 한해 저장 가능한 최대 레코드 건 수가 프라이머리 키 컬럼을 제외한 일반 컬럼 사이즈에 더 큰 영향을 받는다. 어찌되었든 이를 바탕으로 인덱스 깊이에 따른 레코드 건 수와 사이즈를 계산해보면, 깊이 1의 user 테이블 전체 레코드 건 수는 리프 페이지밖에 존재하지 않으므로 최대 52건(16KB)이며, 깊이 2의 user 테이블 전체 레코드 건 수는 927*52 이므로 최대 48,204건(14.4MB)이다. 동일한 방식으로 B-tree 인덱스의 깊이 3은 최대 약 4천4백만 건(13.1GB)이며, 깊이 4는 최대 약 414억 건(11.8TB)이다.

아래는 두 결과를 비교해놓은 표이다.

인덱스 깊이INTBIGINT
153건 (16KB)52 (16KB)
264,978 (19.1MB)48,204건 (14.4MB)
38천만 건 (22.9GB)4천만 건 (13.1GB)
4976억 건 (27.4TB)414억 건 (11.8TB)

그리고 아래는 id가 INT일 때 B-tree 인덱스 깊이에 따른 레코드 건 수와 테이블 사이즈를 나타낸 그림이다.

결론

위 결과처럼 대용량 테이블(테라바이트 기준)이라도 B-tree 인덱스의 깊이가 5단계 이상 깊어지는 경우는 흔치 않을 것이다. 물론 프라이머리 키 데이터 타입을 UUID나 컴파운드로 구성하게 되면 얘기는 달라지겠지만 일반적인 경우에는 인덱스의 깊이가 4단계에서 그친다고 볼 수 있다. 인덱스의 깊이는 DB 성능에 큰 영향을 미치지 않기 때문에(조심스러운 이야기지만) 크게 염려할 필요는 없다.

댓글 남기기