b+tree에 대해..

system77의 이미지

예전부터 궁금했던거지만..

b+tree가 분활되어야 하는 node slots 갯수는 얼마일까가 궁금했습니다.

예전에 어디서 듣긴했는데 까먹었네요

데이터베이스와같이 수백만건의 인덱스라면

node가 분할되어야 하는 시점을 몇개를 잡아야할까요?

대략 depth는 어느정도가 적정할까요?

leafriend의 이미지

node slots이라면 한 edge에 들어갈 node의 갯수를 말씀하시나요?
언젠가 들은 걸로는 파일 시스템의 클러스터 단위로 읽어들이는 게 좋다고 했는데...
정확한 건 아랫 분이 말씀해 주실 듯;

rgbi3307의 이미지


인덱스수 = I,
노드분할시점개수 = k,
depth(트리깊이) = h 라고 했을때,

I = k의 h승,
h = log(k)I, 여기서 k는 log의 밑수.

위의 수식으로 계산될 수 있습니다.
물론 인자들이 조금씩 다를 수 있으나, 위의 수식은 간단하게 일반화시킨 것입니다.
예를들어,
인덱스수 = I = 일백만개 = 10의6승
노드분할시점개수 = k = 10 이면,
depth(트리깊이) = h = log(10)10의6승 = 6.

여기서, k는 기억장소의 특성(페이지크기,접근대기시간,전송시간 등..)을 고려하여
가장 최적화될 수 있는 크기를 구해야 합니다. k는 장치특성에 의존합니다.

BTree를 창시한 Bayer의 논문을 보면, k를 실험(실습데이터)적인 방식으로 산출했는데,
64 < k < 128 범위가 가장 적당하다고 했습니다.(이때, 실험 대상 머신은 IBM 360/44 였습니다)

From:
*알지비 (메일: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))

From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))

hb_kim의 이미지

B+ 트리 등의 자료구조는 한번 데이터를 읽기 시작하면 빠른 속도로 읽을수 있지만, 다른 위치에서 읽기를 시작하면 큰 지연시간을 갖는 하드디스크에 최적화된 자료구조입니다.

따라서 하드디스크의 혹은 하드디스크를 포함하고 있는 스토리지 시스템의 특성에 따라 매개변수를 조정해야 겠죠. 이론상으로는 CPU 의 연산처리 속도도 당연히 변수가 되겠으나, 그동안의 추세는 스토리지가 워낙 느리기 때문에 CPU 의 연산처리 속도가 매개변수에서 빠지는 것이 일반적이었습니다.

다만 한 노드는 스토리지 시스템의 한 블록 크기의 2**n 배가 되어야 하기 때문에 실제로는 RAID 가 있는 스토리지 시스템을 사용하면 다양한 값을 사용하지는 못합니다.

제 생각에는 SSD 가 엔터프라이즈 스토리지 시스템에 도입되면서 스토리지 시스템, 볼륨 매니저, 파일 시스템, 데이터 베이스에서 그 동안 암묵적으로 가정해왔던 많은 법칙들이 깨어지게 될것 같습니다. B+ 트리등의 기존 자료구조가 무용지물이 된다는 것은 아니고, B+ 트리등을 사용하면서 해왔던 많은 가정들이 깨지면서 보다 정교하고 복잡한 방법이 나오지 않을까 생각됩니다.