[MySQL] B-Tree

MySQL에서는 인덱스를 구현할 때 기본적으로 B-Tree를 사용한다. B-Tree에 대해 알아보자.

B-Tree란

B-Tree(Balanced Tree, 균형 트리)는 범용적으로 사용되는 데이터의 구조로, 주로 인덱스를 표현할 때와 그 외에서도 많이 사용된다. 이름에서도 알 수 있듯 균형이 잡힌 트리이다.

노드 Node

트리 구조에서 데이터가 존재하는 공간. 즉, 갈라지는 부분의 '마디'이다.

• 루트 노드는 노드의 가장 상위 노드이고, 나머지 노드들은 모두 이 노드의 자식이다.
• 리프 노드는 가장 마지막에 존재하는 노드이다.

페이지 Page

MySQL이 B-Tree를 사용할 때 이 노드에 해당되는 것이 페이지이다.

• 페이지눈 16Kbyte 크기의 최소한의 저장 단위로, 하나의 데이터만 저장한다고 해도 하나의 페이지를 차지하게 된다.
• 즉, 개념적으로는 노드라고 부르지만, MySQL에서는 노드가 페이지가 되며 인덱스를 구현할 때 기본적으로 B-Tree를 사용한다.

B-Tree 구조

전체에서 값이 한 번만 나오게 하는 방법이다.

그림에서 볼 수 있듯이, 분기가 되는 Einstein, Katz, Singh는 따로 가리키는 포인터가 존재하고,

그 값보다 작은 값들은 왼쪽, 큰 값들은 오른쪽에 위치되어 있다.

 

B+트리와 비교해 보았을 때, B+-트리는 분기가 되는 값을 찾기 위해 leaf node까지 내려가야 하는 것을 볼 수 있다.

즉, B-트리는 분기로 나눠주는 곳에서도 가리키는 포인터가 존재하는 반면, B+트리에는 따로 존재하지 않는다

 

장점

• B+-트리에 비해 트리 노드를 덜 쓴다.
• 찾는 값을 leaf node 도달하기 전에 찾을 수도 있다.
  • B+-트리의 경우 leaf node에 도달해야 찾을 수 있다!

단점

• fanout이 좀 떨어진다.
  • non-leaf node가 더 크다 => depth가 더 커질 수 있음
• insert, delete가 되게 복잡해진다.
  • leaf & non-leaf가 구분되지 않고, 구현이 복잡하다.