[MySQL튜닝]B Tree 인덱스

 

 

MySQL의 인덱스 종류와 B Tree 인덱스에 대해 알아보도록 하겠습니다.

 

1. MySQL의 인덱스 종류

MySQL은 아래와 같은 구조의 인덱스를 제공합니다. 정확히는 MySQL의 스토리지 엔진중 하나인 InnoDB에서 사용할 수 있는 인덱스입니다. MySQL에는 InnoDB 외에도 다양한 스토리지 엔진도 사용할 수 있지만, 대부분 InnoDB를 사용합니다.

• B Tree 인덱스: 원하는 데이터를 빠르게 검색하기 위한 인덱스
• R Tree 인덱스(Spatial Index): 위치나 거리등의 검색에 효율적인 인덱스
• Full text search 인덱스: 문자열 검색에 효율적인 인덱스

RDBMS에서 흔이 말하는 '인덱스' 대부분은 B Tree 구조의 인덱스입니다. (이 글에서도 특별히 언급하지 않으면 B Tree 인덱스를 뜻합니다.) 마찬가지로, 인덱스를 만들때 특별히 옵션을 주지 않으면 B Tree 구조의 인덱스가 만들어집니다.
앞에 글(인덱스 왜 빨라)에서 예를 든 구조(거래처 서류와 서류함) 역시 B Tree 인덱스입니다.

  - https://sweetquant.tistory.com/352

[MySQL튜닝]인덱스 왜 빨라?

실제 RDBMS에서 사용하는 인덱스 구조는 B Tree를 좀 더 발전시킨 B* Tree 또는 B+ Tree 입니다. B Tree, B* Tree, B+ Tree에 대한 차이는 아래 잘 정리된 블로그 글로 대신하도록 하겠습니다. 한 번쯤 읽어보시고 각자 정리해보시기 바랍니다. (사실 아래 글만으로 정리가 안될 수도 있습니다. 대략적인 차이를 이해하는 정도에서 넘어가시는게 좋습니다.)

  - https://wiper2019.tistory.com/301

  - https://ssocoit.tistory.com/217

 

아래의 MySQL 레퍼런스에 의하면, MySQL은 B Tree 구조를 사용한다고 설명되어 있습니다. B+나 B*를 직접적으로 언급하는 부분은 없는거 같습니다. 다만, 많은 책들과 자료에서 MySQL의 인덱스는 B+ Tree라고 설명되어 있습니다.(저 역시 B+ Tree가 맞다고 생각합니다.)

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

MySQL :: MySQL 8.0 Reference Manual :: 15.6.2.2 The Physical Structure of an InnoDB Index

 

2. B Tree 인덱스의 세부 명칭

아래 그림을 통해 B Tree(B+ Tree)를 구성하는 요소별 명칭을 정리해봅니다. 아래 그림은 앞의 글에서 거래처와 서류함을 B Tree 인덱스로 표현한 것으로, '거래처명'으로 B Tree 인덱스를 생성한 경우입니다.

 

 

 

Tree의  가장 위에는 트리 탐색을 시작하는 루트(Root, 뿌리) 노드가 위치합니다. 루트 노드는 하나의 인덱스에 오직 하나만 존재합니다. 루트 아래에는 브런치(Branch, 가지, 또는 미들(Middle)) 노드가 위치합니다. 브런치 노드는 루트에서 가장 아래에 있는 리프(Leaf) 노드를 찾아가는 중간 노드로서, 여러 층이 존재할 수 있습니다.(그림에서는 편의상 한 층만 표현했습니다.) 마지막으로 Tree의 가장 아래에는 리프(Leaf, 잎사귀) 노드가 존재합니다. 리프에는 실제 데이터가 존재하거나 실제 데이터가 위치한 주소 값을 저장합니다. 그리고 리프 노드를 보면 왼쪽부터 알파벳 순서대로 데이터가 입력되어 있으며 근접한 리프 노드끼리는 서로 연결되어 있습니다.

그림을 전체적으로 보면, 나무 뿌리가 가장 위에 있고, 나무 잎사귀가 가장 아래에 있습니다. 나무를 뒤집어서 그린 모양이라고 이해하시면 됩니다.

 

B Tree 인덱스(B+ Tree) 관련해서 중요한 내용을 정리해보면 아래와 같습니다.

• '루트(뿌리), 브런치(가지, 미들), 리프(잎)' 세 개의 요소로 나누어진다.
• 리프에는 실제 데이터 또는 실제 데이터가 존재하는 주소 값을 가지고 있다.
• 리프 노드의 데이터는 정렬되어 있다.
• 근접한 리프 노드는 서로 연결되어 있다.

 

오늘 살펴볼 내용은 여기까지입니다. B Tree와 같은 자료 구조 이야기가 나와 조금 어려울 수 있지만, 한 번쯤은 깊이 공부해볼 필요가 있는 내용입니다.

감사합니다.