졸업 프로젝트로 만들려고 하는 weblog 분석기의 핵심을 담당하게 될 B-tree 작성을 시작했습니다. Key 값의 Update 혹은 Delete 연산은 일어날 일이 없기 때문에 구현을 하지 않을 생각입니다.

우선 File Format 을 대강 잡아놓고, 트리에 값이 내가 의도했던 대로 들어가는 지를 확인하기 위한 Print function 작성을 완료했습니다. Deletion 이 없기 때문에 Node 두 개를 Merge 하는 연산은 필요가 없을 듯 하고, Split 에 어떻게 대처할 지는 이미 노트 위에 모두 정리해두었습니다. Split 시에 Node 를 재정렬하기 위한 QuickSort 와 Search 시에 사용할 BinarySearch 도 구현해야겠네요. (점점 구현해야 하는게 하나 둘 늘어갑니다. 귀찮아지면 Standard C library 에 있는 qsort, bsearch 를 사용할 지도 모르겠습니다.)

예전에 Data Structure 수업 같은걸 들을 땐 ‘그래서 저 트리를 도대체 어떻게 저장해야하는데!!’ 란 생각이 머릿 속에서 떠나질 않았었는데… 막상 포인터 대신 offset 을 이용하는 걸 제외하면 거기서 거기인 거 같습니다.

하여튼 막상 코드 작성을 시작해보니 B-tree 자체를 구현하는 건 그리 오래걸리지 않을 듯 싶어 한시름 덜었습니다. :) 다른 부분들도 여유시간을 충분히 가지고 완성되어 준다면, 디스크 캐쉬까지도 구현해볼 수 있겠네요.

코드는 subversion 을 통해 관리될 예정이며 아래 url 에서 열람이 가능합니다. :)
url: http://trac.unfix.net/browser/btree

덧: 내가 짠 코드지만 왠지 모르게 호감이 간다. 캬캬캬캬!!

Tags: b-tree, log analyser, Project