이전 글에서 Index 사용 배경, Index 자료 구조 중 하나인 Hash Table 을 다뤘다. 이번 글에서는 또 다른 자료 구조 중 하나인 B+Tree 를 다룰 예정이다.
B-Tree 는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. 하지만 아직도 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다. B-Tree 에는 여러 가지 변형된 형태의 알고리즘이 있는데, 일반적으로 DBMS 에서는 주로 B+Tree 또는 B*Tree 가 사용된다.
본론 내용을 이해하기 위해서는 먼저 B-Tree 와 B+Tree 의 차이에 대해 이해하고 있어야 하는데, 해당 내용은 여기 에서 확인할 수 있다. B+Tree 가 B-Tree 와 다른 점은 아래 두 가지로 정리할 수 있다.
① 루트 노드를 포함한 내부 노드는 데이터를 저장하지 않는다.
② 리프 노드는 연결 리스트를 통해 서로 연결되어 있다.
그렇다면, 왜 B-Tree 를 변형해서 위 두 가지 특징을 가지게 했을까?
DB Index 사용 배경과 관련한 위 내용을 기반으로 DB Index 가 디스크 영역에 저장되어 있는 데이터에 대한 I/O 요청 횟수를 줄이는 것과 밀접한 영향이 있다는 것을 쉽게 유추할 수 있을 것이다.
서두에 참조한 이전 글에서 Index 사용 배경을 다루면서, 결국 Index 사용은 Disk 영역에 저장된 데이터에 대한 I/O 요청 횟수를 줄이는 것과 밀접한 관련이 있다고 설명했었는데, B+Tree 가 갖는 두 가지 특성 역시 이 관점의 연장선에서 이해할 수 있다. 지금부터 B+Tree 가 갖는 특성과 I/O 요청 횟수와 어떤 관계를 갖고 있는지 알아보자.
먼저, 두 가지 특성 중 ① 번 특성이 내포한 의미를 알아보자.
[ 그림 1 ] 의 Storage Engine 은 실제 데이터를 디스크 영역에 저장하거나 디스크 영역의 데이터를 읽어오는 역할을 한다. Storage Engine 중 하나인 InnoDB 는 데이터를 읽고 쓰는 단위로 Page 를 사용한다. 또한, 일종의 캐시 역할을 하는 Buffer Pool 역시 데이터를 버퍼링 할 때 Page 단위로 처리하고, Index 역시 Page 단위로 관리된다.
[ 그림 2 ] 는 1, 2, 3, 4, 5 를 순서대로 넣은 B-Tree 고, 각 노드의 키 별로 데이터 포인터를 가지고 있는 것으로 표현했다. (ex - @1, @2 …) 이 때 [ 그림 2 ] 와 같이 각 노드는 Page 로 볼 수 있는데, 각 Page 별로 Entry (K, V) 를 포함하고 있는 것을 알 수 있다. 여기서 K = Index 로 지정된 컬럼, V = 해당 Index 가 실제 저장된 논리 또는 물리 주소 값을 각각 의미한다.
[ 그림 3 ] 은 [ 그림 2 ] 와 같이 1, 2, 3, 4, 5 를 순서대로 넣은 B+Tree 다. [ 그림 2 ] 와 다른 점은 루트 노드를 포함한 내부 노드에는 데이터 포인터를 따로 저장하지 않고, 리프 레벨의 Entry 에서만 데이터 포인터를 가지고 있는 것을 볼 수 있다. 내부 노드에 저장되는 Entry 에는 데이터 포인터가 저장되는 컬럼이 필요 없으므로 해당 공간만큼의 여유 공간이 생긴다.
MySQL InnoDB Storage Engine 은 Page 기본 값 크기로 16KB 가 설정되어 있다. 이 값을 기준으로 각 페이지 별로 저장될 수 있는 Entry 의 수를 생각해보자. 예를 들어, [ 그림 4 ] 와 같이 Page 내 Entry 가 구성되어 있다고 할 때 해당 Page 에는 약 585 개의 Entry 가 저장될 수 있다.
반면 [ 그림 5 ] 와 같이 Page 내 Entry 가 구성되어 있을 때는 약 1024 개의 Entry 가 저장될 수 있다. 앞서 B+Tree 내부 노드에 포함된 Entry 에서는 데이터 포인터 컬럼을 갖지 않는 만큼의 여유 공간이 있다고 했는데, 그 공간을 활용해 더 많은 Entry 를 저장할 수 있게 된 것이다. 그렇다면 한 Page 내에 더 많은 Entry 를 가질 수 있는 것은 어떤 의미가 있을까?
B+Tree 깊이는 MySQL 에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다. 결론적으로 인덱스 키 값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고, 그 때문에 같은 레코드 건수라 하더라도 B+Tree 의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다는 것을 의미한다.
위 인용 내용과 같이 B+Tree 의 깊이가 깊을 수록 더 많은 I/O 요청이 요구되고 결과적으로 처리 시간이 더 오래 소요된다. 따라서 B+Tree 깊이를 얕게 관리하는 것이 중요하다고 볼 수 있다. B+Tree 의 깊이를 얕게 하려면 각 노드가 더 많은 수의 Entry 를 저장하면 되는데, B+Tree 는 B-Tree 와 달리 내부 노드의 Entry 에서 데이터 포인터 컬럼을 제외함으로써 여유 공간을 확보 및 해당 공간을 통해 B+Tree 의 깊이를 얕게 만들고 이를 통해 I/O 횟수를 줄여 데이터 조회 처리 성능을 더 효율적으로 할 수 있기 때문에 일반적으로 B-Tree 를 변형한 B+Tree 를 사용한다고 이해할 수 있다.
① 루트 노드를 포함한 내부 노드는 데이터를 저장하지 않는다.
② 리프 노드는 연결 리스트를 통해 서로 연결되어 있다.
그렇다면, ② 은 어떤 의미를 내포하고 있을까?
② 에서의 연결은 [ 그림 6 ] 의 리프 노드 간의 관계를 의미하고, ② 특성은 Index 를 활용한 Range Scan 과 밀접한 관련이 있다. B-Tree 에서 Range Scan 을 하려고 하면 각 Page 에 저장된 Entry 를 모두 탐색해야 한다. 각 Entry 에서 데이터 포인터를 관리하기 때문이다. 반면, B+Tree 에서는 Range Scan 을 더 효율적으로 처리가 가능하다. [ 그림 6 ] 과 같이 리프 레벨의 Page 는 서로 연결 리스트와 같은 자료 구조를 통해 연결되어 있다. 따라서 Range Scan 의 시작점을 찾기 위해 한 번만 리프 레벨에 도달하면, 그 이후부터는 연결 리스트를 통해 주어진 범위만큼 탐색하면 된다. 또한 이 과정에서 더 적은 페이지를 탐색하게 되고 따라서 더 적은 I/O 요청을 통해 Range Scan 이 가능하다는 점에서 B-Tree 대신 B+Tree 를 사용한다고 이해할 수 있다.
Real MySQL 8.0 | 8장 인덱스 mysql 인덱스 정리 및 팁 DB Index 입문 데이터베이스 인덱스란?