2022. 6. 17. 15:13ㆍ데이터베이스
이 글은 'Real MySQL 8.0 개발자와 DBA를 위한 MySQL 실전 가이드'를 보고 학습한 내용을 정리한 글입니다.
B-Tree 인덱스는 인덱스를 구성하는
1. 칼럼의 크기와
2. 레코드의 건수
3. 유니크한 인덱스 키 값의 개수
등에 의해 작업 성능 영향을 받습니다.
InnoDB 스토리지 엔진에서, 주기억장치(하드디스크)에 데이터를 저장하는 가장 기본적인 단위를 페이지, 블록이라고 합니다. 이론적으로 디스크의 모든 읽기와 쓰기는 페이지 단위 미만이 될 수 없습니다.
또, 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링(캐싱) 하는 기본 단위입니다. 인덱스 구조에서 루트, 브랜치, 리프 노드를 구분하는 기준이 바로 이 페이지 단위입니다.
흔히 오해하기 쉬운 것이, B-Tree가 Binary의 B를 의미하고 있다는 오해입니다. 물론 내부구조를 이진트리로 구성해도 작동은 되겠지만, 노드당 자식을 최대 2개만 갖게 되어 트리의 depth가 너무 깊어지는 현상이 일어나게 됩니다. 즉, 디스크 랜덤 I/O가 비정상적으로 늘어나는 결과를 초래하게 됩니다. 성능하락도 당연합니다.
결론적으로 B-Tree의 B는 Balanced를 의미합니다. https://ko.wikipedia.org/wiki/%EC%9E%90%EA%B0%80_%EA%B7%A0%ED%98%95_%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC 에 따르면, B-Tree는 삽입과 삭제 연산에서 자동으로 트리의 depth를 최소화하여 유지하는 트리라고 합니다. 2개를 초과하는 자식노드를 가질 수도 있고, 어느 한 쪽으로 쏠리는 트리의 모양을 가지지도 않아서 최악의 경우에도 이진 트리보다 훨씬 좋은 성능을 보입니다.
그런데, 이진 트리보다 성능이 좋다고 해서 무작정 써도 되는 것은 아닙니다.
# 인덱스를 구성하는 칼럼의 크기
B-Tree는 한 페이지에 몇 개의 노드를 저장할 수 있을까요? 이진트리의 2개보다는 많을 것 같다는 예상이 듭니다.
최악의 경우를 따져보겠습니다. 페이지의 크기를 InnoDB의 기본값인 16KB라고 가정하고, 인덱스의 키 크기는 페이지의 최대 크기에 비례하기 때문에 가장 큰 길이의 인덱스 크기는 페이지가 16KB인 경우에 3072B 입니다. 각 노드는 자식노드의 주소를 K-V 형태로 갖고 있습니다. 자식노드의 주소의 크기 값 을 12B라고 가정한다면 각 노드는 3084입니다.
결론적으로 각 페이지는 최악의 경우 16384 / 3084 = 5.31258106355 개의 노드를 가질 수 있게 됩니다. 여전히 이진트리보다는 많은 노드를 포함하지만 tree의 depth가 너무 높아져서 성능은 정말 나쁠 것 같네요. 이 최악의 경우를 교훈삼아 인덱스를 구성하는 칼럼의 크기를 적당히 작은 크기로 유지하는 것이 성능상에 이점이 많을 것이라 생각합니다.
그렇다면, 최선의 경우에 페이지는 몇 개의 노드를 포함할 수 있을까요?
동일한 16KB 페이지에서, 레코드의 키 타입을 int로 지정하면 각 노드는 16B만을 차지하게 됩니다
'데이터베이스' 카테고리의 다른 글
| InnoDB의 레코드락에 대한 궁금점 (1) | 2022.07.15 |
|---|---|
| MySQL8.0 Error Code: 1071. Specified key was too long 해결법 (1) | 2022.07.15 |
| ORDER BY rand() 쿼리문 튜닝하기! (0) | 2022.05.23 |
| 서비스로직과 트랜잭션 분리 [SPRING] (1) | 2022.05.12 |
| [Real MySQL] 슬로우 쿼리 로그 확인 (0) | 2022.05.12 |