[회고록] B+Tree 프로젝트

B+Tree 프로젝트 Github 링크

21.01.07 ~ 21.01.14

C언어의 포인터만을 이용하여 DB의 index를 구현할 때 많이 사용한다고 하는 B Tree와 B+Tree를 구현하는 프로젝트였습니다. C언어를 처음 공부하였기 때문에 포인터를 사용하는데에 익숙하지 않았지만, 빠르게 C언어에 공부할 수 있는 기회가 되었습니다.

어려웠던 점

1. C언어의 포인터에 익숙해지는 시간이 필요했습니다. C언어를 공부하기 이전에는 포인터의 역할이 다른 언어의 참조와 비슷하다고 생각했습니다. 생각과 다르게 C언어는 더욱 기계 친화적인 언어여서 메모리 할당에 대한 이해가 필요함을 느꼈습니다.

2. 코드를 짜기 전 설계과 검증에 많은 시간을 할애했습니다. 오랜시간 설계를 진행하다 보니 심적으로(?) 힘든 부분도 있었습니다. B트리를 구현하는데는 두가지 방법이 존재하였고, 두가지 방법을 모두 공부하고 이해하는 과정을 거쳤습니다. 플로우차트 그려보고, 어떤 방식으로 동작하는지 식으로 동작하는지 고민해보면서 어떤 방법이 더 합리적인 과정인지 고민하는 시간을 가졌습니다.

3. C언어는 가독성이 많이 떨어지는 언어라는 생각이 들어 가독성 있는 깔끔한 코드에 대한 고민을 하게 되었습니다. 함수명, 변수명 등 명시적인 규칙들을 가질 수 있게 작성하려 노력하였고, 중복되는 코드들을 함수로 처리하는 등으로 수정하였습니다.

4. 자식 노드들을 옮기는 과정에서 인덱스를 잘못 계산해서 정보를 덮어쓰는 현상이 발생하였습니다. 포인터만을 사용하기 때문에 인덱스를 굉장히 많이 사용하는 만큼 인덱스에 대한 계산이 어려웠습니다. 또한

5. malloc 한 변수를 free 과정에서 오류를 경험하였습니다. 트리의 모든 노드를 지우는 상황에서 발생하였는데, 비어있는 루트노드까지 지워버리는 경우가 발생하였습니다. 이 상황에서 삽입 또는 삭제를 시도하게 되면 루트노드가 존재하지 않아 삽입이 시도되지 않고 오류가 발생하였습니다. 다시 삭제를 시도하는 경우에는 기존에 있던 루트노드를 free해주고, 새로 루트 노드를 만들어 tree를 만들어줘야 이 다음에 insert할 때 에러가 발생하지 않는다.

6. malloc 한 다음에는 꼭 null을 체크하는 과정을 거쳐야 한다는 것을 알았습니다. malloc 시 메모리를 항상 할당하는 것이 아니기 때문에, 주소값이 NULL인지 확인해야 했습니다.

7. 컴파일러와 환경에 따라 코드가 실행되기도 하고 안되기도 하는 상황이 발생하였습니다. 윈도우 + vscode 환경에선 잘 돌아가는 코드가 맥 + clion 환경에서 돌아가지 않는 상황이 발생하였습니다. 함수의 반환이나 배열의 인덱스를 넘어가는 경우 등에서 암묵적으로 수행해주는 컴파일러와 엄격하게 에러를 반환해주는 컴파일러가 있다는 것을 알게 되었습니다.

8. 함수의 인자로 받아온 값을 저장한 배열을 만들었을 때, 일부 배열의 원소들이 같은 값을 가지는 상황 발생 => 함수 사용시에 stack영역에서 같은 함수를 실행했다, 종료했다 하기 때문에 같은 메모리 영역을 사용하여

배운점과 성과

1. 악명 높은 C언어와 포인터에 대해 익숙해지는 시간이었습니다. 포인터에 대한 깊은 공부도 좋지만 실제 프로젝트를 통해 직접 사용해보니 확실히 이해되는 경험을 하게 되었습니다. 이중 포인터의 활용, 배열과 문자열 모두 포인터로 구현되어 있다는 점이 신기했습니다. C는 그저 포인터밖에 모른다고 생각하면 오히려 C언어를 이해하기에 좋은 상황이 생기는 이상한 경험(?)도 하였습니다.

2. DBMS의 인덱스에 대한 이해를 할 수 있었습니다. 글로만 읽었던 인덱스의 개념보다 인덱스 구현에 직접 사용되는 자료구조를 구현하는 과정을 통해 구현 과정까지 이해할 수 있던 시간이었습니다.

3. 코드를 짤 때 많은 부분을 고려하면서 코딩하는 과정이 매우 중요함을 다시한번 상기하는 기회였습니다. 함수를 일반화하여 코드의 간결화하고, 함수의 반환 등에서 에러를 발생하는 경우는 없을지 고민하면서 어떤 환경에서도 적용 가능하도록 예외적인 에러가 없는 코드를 작성해야 겠습니다.

4. 구조에 대한 설계에 많은 시간을 들인 만큼 디버깅 시간이 확실히 줄어드는 경험을 하였습니다. 많은 사항을 고려하고, 테스트하면서 코드를 설계하는 습관을 길러야 겠습니다.

5. 성능을 개선하는 경험을 하였습니다. 키값을 삭제하는 불필요한 연산을 수행하지 않게 하여 구현도 간편하고 성능적인 부분도 개선하는 효과를 얻을 수 있었습니다.

앞으로 해보고 싶은 공부

1. DBMS의 인덱스를 어떻게 만들고, 어떤 방법으로 효율적인 탐색을 진행하는지 알게된 경험이었습니다. 그렇다면 NOSQL은 해쉬 이외에 어떤 방법으로 효율적인 탐색을 수행하는지 공부해보려 합니다.

2. 대표적인 다른 종류의 트리인 레드블랙 트리에 대해서 공부해 보고싶습니다. B 트리와 마찬가지로 대중적인 트리인 만큼 시간을 내어 공부할 것입니다.

3. 이중포인터를 사용하여 여러가지 값들을 바꾸고 저장하는 과정을 익혔습니다. 이후 C언어의 추가적인 문법들에 대해 공부하고, 이중 포인터 이상의 다중 포인터를 활용하는 방법들에는 뭐가 있는지 공부할 생각힙니다.