이 글은 제가 MySQL Power Group에 예전에 포스팅한 자료입니다.
참고 : http://cafe.naver.com/mysqlpg/189

과거와는 다르게 데이터 사이즈가 비약적으로 커지고 있습니다. 특히, 최근 들어 SNS 서비스가 성황을 이루면서, 개인화된 데이터는 날이 갈수록 기하 급수적으로 늘어나고 있습니다. 최근 Fratical Index 기반의 TokuDB가 오픈 소스로 풀리면서 재조명을 받고 있는데, 이에 대해서 간단하게 설명해보도록 하겠습니다.

B-Tree?

TokuDB에 논하기에 앞서, 전통적인 트리 구조인 B-Tree에 대해 알아보도록 하죠.

일반적으로 RDBMS에서 인덱스는 대부분 B-Tree기반으로 동작하는데, 크게는 Internal Node와 Leaf Node로 나뉩니다. Internal Node는 데이터를 어느 방향(작으면 왼쪽, 크거나 같으면 오른쪽)으로 보낼 지 결정하는 Pivot과 다음 Pivot의 위치를 알려주는 포인터로 구성됩니다. Internal Node의 가장 마지막 포인터는 Leaf Node를 향하는데, Leaf Node에는 보통은 데이터가 저장이 되죠.