B-Tree 프로젝트

오늘부터는 B-Tree에 대한 설명과 내 코드의 전반적인 설명을 마치고, 매일 새로 짜거나 수정한 코드들에 대해 정리해보려고 한다. 내가 짠 B-Tree 관련 코드들은 내 깃헙 레포지토리¹를 참고하면 된다.

왜 1일차인가?

제목을 읽어보면 알겠지만, 이번 일지가 B-Tree 프로젝트 개발일지 ‘1일차’이다. 분명 코드를 짜기 시작한 것은 훨씬 전이긴 하지만, 이렇게 이름을 붙인건 개발일지를 작성한 것은 1일차이기 때문이다.

다른 개인 프로젝트를 진행할 때도 이런 식으로 진행할 것이다. 그러나 혼선을 줄이기 위해 코드 작성을 시작하기 전에 프로젝트에 필요한 배경지식들을 우선 정리하고 코드를 시작하는 동시에 개발일지를 시작할 것이다.

BKeyList의 멤버 함수들

이제 본격적으로 내가 작성한 BKeyList 코드들에 대한 내용을 정리해보겠다. 우선 BKeyList에 내가 만들어둔 멤버 함수들은 다음과 같다.

함수명	접근 지정자	반환 값 자료형	기능
BKeyList(size_t order)	public		B-Tree의 order를 매개변수로 받아 BKeyList를 생성한다.
~BKeyList()	public		BKeyList를 소멸시킨다.
findIndex(const T& key)	public	size_t	리스트에서 매개변수로 들어온 키값의 인덱스를 반환한다. 만약 해당 키값이 존재하지 않는다면, B-Tree의 노드에서 접근해야 하는 자식 노드의 인덱스를 반환한다.
insert(const T& key, size_t idx)	private	void	리스트의 특정 인덱스에 key값을 넣고, 해당 인덱스와 뒤의 인덱스에 key값이 있었다면, 한 칸씩 뒤로 밀어준다.
insert(const T& key)	public	void	리스트에 정렬된 상태를 유지한채로 키를 삽입한다.
remove(const T& key, size_t idx)	private	bool	리스트의 해당 인덱스의 키값이 매개변수로 들어온 키값과 일치하면 리스트에서 삭제하고 뒤에 있는 값들을 앞으로 밀어준다. 해당 인덱스의 키의 삭제 성공 여부를 반환한다.
remove(const T& key)	public	int	리스트가 정렬된 상태를 유지한채로 키를 삭제한다. 삭제에 성공히먄 -1을 반환히고, 실패하면 B-Tree의 노드에서 접근해야 할 자식 노드의 인덱스를 반환한다.
splitRequired()	public	bool	이 리스트를 포함한 노드에서 분할이 일어나야 하는가에 대한 여부를 반환한다.
split()	public	BKeyList*	BKeyList의 분할을 진행한다. 새로운 BKeyList를 생성하고, 기존 리스트의 뒷부분 요소를 삽입한다. 새로 할당된 뒷부분의 BKeyList의 포인터를 반환한다.
operator	public	T&, const T&	[] 연산자를 이용하여 리스트의 특정 요소에 접근한다.
std::string traverse()	public	std::string	리스트의 요소들을 순회하고 그 결과를 반환한다.
getCurrentSize()	public	const size_t	현재 리스트에 존재하는 요소의 개수를 반환한다.

수정사항

오늘 새벽에 수정하여 push한 코드들의 수정사항은 다음과 같다.

1. insert 함수 책임 분리: 기존의 코드에서는 insert 함수의 반환값을 통해 노드의 분할이 필요한지 여부를 함께 반환하도록 했지만, insert가 삽입하는 역할만 수행하도록 splitRequired라는 함수를 따로 만들어 기능을 분리하였다.

2. findIndex 함수 수정: 기존의 findIndex 함수는 재귀함수였으나, 반복문 이용한 이분탐색을 수행하도록 수정하였다.

3. BKeyList 테스트벤치 삭제 부분 추가: BKeyList가 제대로 작동하는지 확인하기 위한 테스트벤치의 코드에서 삭제도 시험해볼 수 있게 수정하였다. 아직까지는 제대로 작동하는 것으로 확인되었다.

마무리

BKeyList는 프로젝트 초기부터 가장 집중적으로 만들었던 코드로, 거의 완성되었다고 판단하여 각 함수에 대한 설명을 제공하는 동시에 수정사항도 간단하게 언급하였다. 그러나, BNode나 BTree 클래스의 경우에는 아직 함수들이 충분히 구현되지 않아 글을 작성하는 방식이 조금 달라질 것이다.

일지별로 구현하고자 하는 각 기능들과 관련된 함수들을 위주로 다룰 것이며, 수정사항에서 코드의 변경점을 직접 그 코드를 삽입하여 함께 언급하는 방식으로 개발일지를 진행할 것이다.

드디어 본격적으로 개발일지가 시작된다는 사실에 가슴이 두근거린다. 이 두근거림을 잊지 말고 열심히 일해야겠다. 오늘의 개발은 여기까지!

---

1: https://github.com/ChoiCube84/B-Tree-cpp-implementation

---

---