[야매 알고리즘] B-tree(1)

야매 알고리즘?

알고리즘의 정확한 정의나 의미를 다루지 않고 핵심적인 작동 원리와 코드 예제를 정리하기 위한 시리즈입니다.

전부 짚고 넘어가면 좋겠지만 그럴 지식도 없고, 공부하는 것보다 정리하는데 더 많은 에너지와 시간을 소모할 것 같아서, 기억을 되살리기 위한 아카이브 정도로만 사용할 수 있게 간단하게 정리할 예정입니다.

 

왜 B-tree인가?

B-tree는 AVL tree나 RB tree와 같은 self-balancing tree의 일종이다.

B-tree의 가장 큰 특징이자 장점은 disk input/output 연산을 최소화하는 데 있다.

실무에서 다루는 데이터의 크기는 절대로 메인 메모리에 한 번에 올릴 수 없을 정도로 크기 때문에, 데이터에 접근하기 위해서는 disk access는 필연적이다. 하지만 HDD는 메모리와 달리 물리적인 동작을 통해 데이터를 읽고 쓰기 때문에, 메인 메모리에 접근하는 것 보다 약 10만배 이상 오래 걸린다고 한다.

따라서 이 disk access를 최대한 효율적으로 해야, disk access time 때문에 발생하는 병목 현상을 최소화 할 수 있다.

 

B-tree의 대표적인 특징은 다음과 같다.

1. 자식 노드의 개수를 최대 M개 가질 수 있다. (단, M >= 2) (RB tree와의 가장 큰 차이점이라고 볼 수 있다)
2. 각 노드는 최대 M - 1개의 key를 가질 수 있다.
3. 각 노드에 들어있는 key는 정렬되어있다. 이 특징을 활용해서 마치 binary search tree처럼 search할 key가 어느 노드에 있는지 알 수 있다.
4. Root 노드에서 모든 leaf 노드까지의 경로 상의 간선 개수가 동일하다. 즉 모든 leaf node의 level이 동일하다.
5. B-tree의 height는 항상 O(logN)이다.

왜 이렇게 되는지, 또 다른 디테일한 특징들에 대해서는 다른 글에서 설명하겠다.

 

아무튼 이러한 특징에 의해서 B-tree로 데이터를 저장하고 관리하면 disk access time을 최적화 할 수 있다.

• HDD는 데이터가 실제로 기록되는 여러 개의 platter(원판)와, platter에 접근하는 arm과 head로 구성된다.
• Platter가 물리적으로 회전하고, arm과 head는 platter의 특정 track(platter상의 동심원)을 읽기 위해 역시 물리적으로 이동한다. 데이터를 읽기 위해 arm과 head가 track과 track 사이를 움직이고, platter가 회전을 하는 것은 물리적 움직임이기 때문에 여기서 상대적으로 많은 시간이 소요되고, 이로 인해 병목 현상이 일어난다.
• 이런 문제를 해결하기 위해 2^11 ~ 2^14 byte 크기의 page 단위로 disk access를 한다. 즉 한번 read/write를 할 때 page 전체를 read/write 해서 disk access 횟수를 줄이는 것이다.
• Page 단위로 read/write를 한다는 disk access의 특징을 적용하여, B-tree의 각 노드의 크기 (key와 자식 노드를 가리키는 포인터 등이 저장되어 있음)를 page 크기와 동일하게 정하면, disk에 저장되어 있는 B-tree의 한 노드를 disk access 한 번에 읽을 수 있다.
• 만약 10억개의 key를 다루는 상황에서, 노드가 최대 1000개의 key를 가질 수 있는 B-tree를 사용한다면, 크기가 작은 root 노드는 메인 메모리 위에 있다고 가정했을 때, B-tree의 어떤 key를 search 하든 간에 최대 disk access 2번 만에 search가 가능하다.

10억개의 key를 가진 1001 degree의 B-tree

 

뭔가 자식 노드가 많고, key가 여러개 들어갈 수 있어서 그런지 생겨먹은 모습은 AVL tree나 RB tree처럼 예쁘게 생기진 않았지만, disk access 횟수를 고려한 구조만큼은 정말 아름답다.

결론적으로는 disk access 최적화가 B-tree의 목적이라고 볼 수 있다. 실제로 B-tree의 개선판(?)인 B+ tree는 실제로 많은 데이터베이스에서 사용되고 있다.

 

참고로 B-tree의 B가 무슨 단어의 약자인지는 알려진 바가 없다. 위키피디아에서 B-tree 를 검색해보면

Bayer and McCreight(B-tree를 고안해 낸 사람) never explained what, if anything, the B stands for: Boeing, balanced, broad, bushy, and Bayer have been suggested.
McCreight has said that "the more you think about what the B in B-trees means, the better you understand B-trees."

출처: https://en.wikipedia.org/wiki/B-tree

 

라는 조금 황당한 정보를 발견할 수 있다.

 

 

참고

Thomas H. Cormen 외, 『Introduction To Algorithm』