오늘은 내가 현재까지 짠 B-Tree 코드에 대해서 설명해볼 것이다. 코드를 한줄한줄 분석하기 보다는 큰 구조를 위주로 설명을 할 것이다. 코드는 내 깃헙 레포지토리1를 참고하면 된다.
이 프로젝트에서 B-Tree를 구현하기 위해 3가지 클래스를 만들었다. 각각 BKeyList, BNode, BTree 클래스이다.
BKeyList 클래스: B-Tree의 노드에서 키값들을 저장하는 리스트의 역할을 한다. 키값의 삽입과 삭제가 일어나더라도 내부 키값들이 정렬된 상태를 유지하도록 하며, 이분탐색을 통해 키값을 검색한다.
BNode 클래스: B-Tree의 ‘노드’ 역할을 수행한다. 리프 노드와 그렇지 않은 노드의 기능을 모두 수행하며, 이는 내부 변수로 리프 노드 여부를 저장한다. 키값들을 저장할 BKeyList의 포인터, 자식 노드들의 포인터들을 저장하는 배열을 가지고 있다.
BTree 클래스: B-Tree 자체의 역할을 수행한다. 루트 노드의 포인터를 가지고 있으며, B-Tree를 사용하기 위해 직접 사용되는 클래스이다.
앞서 언급했던 깃헙 레포지토리에도 설명이 되어있지만, 이 B-Tree에서 수행하는 큰 4가지 기능은 다음과 같다.
삽입 (Insert): B-Tree에 키값들을 삽입하는 역할을 수행하며, 이 B-Tree에서는 중복된 키값이 삽입을 허용한다. 현재 가장 열심히 구현중인 기능이다.
삭제 (Insert): B-Tree의 키값들을 삭제하는 역할을 수행한다. 가장 구현하기 어려울 것으로 예상된다.
검색 (Search): B-Tree에서 특정 키 값이 존재하는지 확인하는 역할을 수행한다. 삽입과 삭제에도 사용되는 기능이다.
순회 (Traversal): B-Tree에 있는 모든 키값들을 특정 규칙에 따라 전부 나열하는 역할을 수행한다. Preorder, Postorder, Inorder 방식의 순회가 가능하다.
BKeyList, BNode, BTree 순서로 다음과 같은 기능들을 구현하고 있으며, 그 이유는 앞에 있는 클래스들에서 다음과 같은 기능이 구현되어야 뒤에 따라오는 클래스들에서 기능을 제대로 작동시킬 수 있기 때문이다. 현재는 BKeyList에서 위의 기능들이 거의 구현이 되었으며, 제대로 작동하는지 검증하는 단계에 있고, BNode의 삽입 기능을 구현하는 단계에 있다.
내일부터는 거의 구현이 완료된 BKeyList의 주요 함수들이 제대로 작동하는지 검증하는 시간을 가지고, 해당 함수들의 기능과 동작에 대해 정리해보겠다.
오늘의 개발은 여기까지!
1: https://github.com/ChoiCube84/B-Tree-cpp-implementation