[5.6장] Fractal-Tree 인덱스

[jjj0611]

p.241 Fratal-Tree는 이러한 B-Tree의 단점을 최소화하고, 이를 순차 I/O로 변환해서 처리할 수 있다는 것이 가장 큰 장점이다. 그래서 Fractal-Tree를 스트리밍(Streaming) B-Tree라고도 한다.

질문 : Fractal-Tree의 동작 원리에 대해서 자세한 언급이 없던 것 같아요. 어떻게 순차 I/O로 변환해서 처리할 수 있을까요? p.242에서 언급한 인덱스 키 값을 클러스터링 한다는 것과 관련이 있을까요? 만약 관련이 있다면 InnoDB에서도 클러스터링 키를 사용한다고 했는데, 그것과는 어떻게 다를까요? 그리고 그 변환 과정 때문에 Streaming B-Tree라는 이름이 붙은 이유가 뭘까요?

[giantim]

Tokutek은 percona라는 회사에 합병되었습니다. 그래서 Fractal-Tree와 TokuDB에 관한 모든 자료는 percona의 홈페이지에서 검색했습니다.
how fractal tree works라는 문서를 보고 Fractal Tree의 데이터 처리 과정을 정리한 내용입니다. 잘못된 점이 있다면 지적해주세요 :)

Fratcal Tree와 B-Tree의 노드의 차이점은 여러개가 있습니다. 먼저 각 노드의 크기자체가 다릅니다. B-Tree의 경우 16kb로 매우 작은 크기이지만 Fractal Tree의 경우 4mb 정도의 훨씬 큰 크기를 갖습니다. 질문주신 I/O에 관련해서 가장 큰 차이를 갖는 부분은 각 노드마다 message buffer라는 버퍼를 갖는다는 것입니다. 그림으로 보면 다음과 같습니다.

데이터 옆에 메시지 버퍼가 있어서 테이블을 조작하는 명령어를 담고 있습니다. 이 버퍼는 리프 노드를 제외한 루트 노드, 브랜치 노드에 존재합니다. 먼저 명령이 들어왔을 때 루트 노드의 버퍼에 저장됩니다. 명령이 점점 쌓여서 루트 노드의 메시지 버퍼가 가득 차면 가장 먼저 들어온 명령을 적절한 브랜치 노드의 메시지 버퍼에 전달합니다. 이런식으로 명령을 계속 하위 노드의 메시지 버퍼로 전달하다 가장 마지막 리프 노드에 전달되면 해당 명령을 수행합니다.
이 메시지 버퍼의 존재 때문에 순차 I/O로 데이터 조작 명령을 처리할 수 있다고 생각합니다. 문서에 보면 B-Tree의 경우 Slow for High Entropy insertion 이라고 설명되어 있습니다. high entropy란 분포도가 넓다는 뜻입니다. 예를 들어 1, 5, 100000, 10000000000, 432, 6 라는 데이터를 저장하는 경우를 생각해보겠습니다. B-Tree의 경우 데이터를 단건으로 처리하고 있으므로 1 저장 -> 5 저장 -> 100000 저장 -> ... 의 순서로 저장할 것입니다. 그러면 1을 저장해야 하는 노드로 이동 -> 5를 저장해하는 노드로 이동 -> 100000를 저장해야 하는 노드로 이동 -> ... 이런 식으로 계속해서 디스크의 헤드를 이동시켜야 합니다.

Fractal Tree에서 위의 예시와 동일한 데이터를 저장할 때 노드의 메시지 버퍼에 명령을 모았다가 메시지 버퍼가 가득 찾을 때 명령을 실행하므로 디스크 헤드의 큰 이동 없이 명령을 수행할 수 있기 때문에 순차 I/O로 처리할 수 있다고 생각합니다. 이점이 B-Tree 역시 저장하는 인덱스 키를 클러스터링 하지만 순차적으로 명령을 처리하지 못하는 점이라고 생각합니다.

자료를 좀 더 찾아봤지만 Fractal Tree 인덱스를 Streaming B-Tree라고 표현한 자료는 찾지 못했습니다. 하지만 위에서 설명한 과정 때문에 그런 이름이 붙지 않았을까요? :)

[giantim]

조회 명령을 어떻게 순차 I/O로 처리하는지 다시 찾아보면 좋을 것 같네요 :)