B Tree 구현
Introduction to Algorithms 라는 알고리즘책(한국어판도 있다)에 B트리 설명이 굉장히 잘 되어있다. 책에 B-tree의 기본 개념과 용도에 대해 상세하게 설명이 되어있다.
아울러 Insertion에 대한 의사코드가 나와있어서 C로 B-tree를 쉽게 만들 수 있었다. Deletion의 경우 의사코드는 없지만, 굉장히 명확하게 작동원리가 쓰여있다. 혹시나싶어 찾아보니, 책 연습문제로 Deletion 의사코드를 작성하는 것이 있었고, 구글링 결과 답지를 찾을 수 있었다. 허나 답지의 Deletion 의사코드는 잘못 된 부분이 있었다(고 생각한다). 이에 의사코드보다는 책에 적혀있는 작동원리를 기반으로 코딩하니, 잘 작동되었다.
B-tree와 B+tree를 구현할 때에 주의할 점은 유튜브에 나오는 영상들의 퀄리티가 그닥 좋지 않다는 것이다. 유튜브도 보고 책도 보았지만, 책에 나온 구현방법이 훨씬 더 명확하고 이해하기도 좋았다. 책이 3판까지 나오고, 한국어로 번역된 대에는 다 이유가 있다!!
B+ Tree 구현
슬프게도 책에 나와있지 않다. 그러나 B Tree를 구현하고 나니 B+ Tree를 구현하는 것은 그닥 어렵지 않았다. B+ Tree의 작동원리를 곰곰히 따져보니 차이점은 주로 트리의 Leaf 노드들에서 생겼다. 이때의 경우만 잘 고려한다면 B Tree와 거의 유사한 코드로 구현할 수 있었다.
아울러 B+ Tree만의 특징이라고 할 수 있는, Leaf들을 연결해준것은, 그저 Node 구조체에서 link라는 멤버를 추가하여 구현할 수 있었다.
책
https://mitpress.mit.edu/books/introduction-algorithms-third-edition
아이패드 메모
