SQLite의 페이지는 대부분 Btree 페이지입니다.
테이블이나 인덱스는 B+ tree 구조로 저장되지요. 다시 말하면 각각의 B+ tree 페이지는 곧 B+ tree의 하나의 노드가 됩니다. 책에서 보던 B+ tree 노드는 대개 3~5개 정도의 아이템을 갖고 있지만 실제 SQLite같은 DB에서는 페이지 사이즈가 1K이므로 키가 int라면 4바이트, 단순히 계산하면 256개의 아이템이 저장되는 셈입니다.
B+ tree에서 하나의 노드는 아래와 같이 표현되지요.
Ptr은 자식 페이지를 가리키는 포인터(혹은 SQLite의 경우 페이지 번호), Key는 키값입니다.
Ptr(0)이 가리키는 페이지나 그 하위 페이지들은 Key(0)보다 작거나 같은 키값을 가지는 데이터를 갖고 있고, Ptr(1)은 Key(0) < k <= Key(1)인 k 키값의 데이터들을 갖고 있는 것입니다.
바이너리 트리에 비해 데이터가 매우 많아져도 낮은 depth로 데이터를 찾을 수 있습니다. 물론 페이지 내에서 또 binary search가 이루어지므로 그 비용을 포함하면 결국 검색횟수 자체는 비슷하겠지만요.
그러면 실제 SQLite의 페이지는 단지 위처럼 Key와 Ptr값만을 주루룩 저장하고 있느냐 하면 그것은 물론 아닙니다. 하나의 SQLite B+tree 페이지는 다음과 같은 구조로 이루어집니다(SQLite btreeInt.h의 주석에서 발췌).
셀(cell)이란 것은 테이블 페이지라면 하나의 레코드가 됩니다. 레코드에 레코드 정보와 rowid를 덧붙여서 하나의 cell이 만들어집니다. 인덱스 페이지라면 키값과 키에 해당하는 데이터가 있는 rowid를 합쳐서 cell이 만들어집니다.
중요한 것은 B-tree 모듈에서는 이게 테이블인지 인덱스인지는 별로 상관이 없이 프로그래밍 되어 있다는 것입니다. 그냥 키/데이터로 이루어진 cell이 주어지면 key 순서에 맞게 저장하거나 찾아주기만 하면 되는거지요.
그럼 각각의 영역에 대해 알아볼까요. 파일 헤더는 첫번째 페이지에만 존재하는, DB 파일에 대한 정보를 담고 있습니다.
중요한 건 두번째인 페이지 헤더부터입니다. 페이지 헤더는 다음의 정보들을 갖고 있습니다.
페이지 헤더 다음에는 cell pointer array가 있는데 이는 실제 데이터가 저장된 cell을 가리키는 포인터의 배열입니다. 그리고 cell은 마지막의 cell content area에 저장되죠. 이 포인터 배열은 페이지 헤더 다음부터 정방향으로 씌어지면서 영역이 늘어나게 되고, cell content area는 페이지의 끝에서부터 역방향으로 씌어지면서 늘어나게 됩니다. 그래서 unallocated space는 그 둘의 가운데에 위치하게 됩니다.
예를 간단히 들어보겠습니다. 1024 바이트 크기의 leaf 페이지가 깨끗한 상태라면 페이지 헤더 8바이트를 제외한 1016 바이트가 unallocated space가 되겠죠. 이 때 10바이트의 cell이 페이지에 들어온다면 현재 페이지는 빈 상태이므로 페이지의 맨 마지막에 씌어지게 됩니다. 그러면 시작 바이트는 1014바이트가 되겠죠? 이 값이 바로 cell pointer array의 첫번째에 씌어지게 됩니다.
그리고 마지막으로는 페이지 헤더의 셀 갯수가 0에서 1로 바뀌고 cell content area의 시작 바이트 옵셋이 1014로 기록됩니다.
그럼 페이지 레이아웃이 대략 다음과 같이 됩니다(클릭해서 보세욤).
cpa는 cell pointer array의 약자입니다. 아래의 숫자들은 페이지 옵셋이고요.
여기에 추가로 4바이트의 셀이 또 씌어진다고 하면 아래와 같이 변하겠죠.
즉 이런 식으로 content pointer array는 앞에서부터 씌어지고 cell content area는 뒤에서부터 씌어지게 됩니다. 이런 구조는 다른 데이터 베이스에서도 주로 쓰이는 형태입니다.
왜 이런 구조가 필요한가? 이는 근본적으로 들어오는 cell의 크기가 일정치 않기 때문입니다. fix된 크기의 데이터라면 관리가 쉽지만 그렇지 않을 경우 업데이트나 삭제, 삽입이 연속적으로 이루어질 경우 공간을 제대로 활용하기가 쉽지 않습니다.
그리고 실제 정렬은 개당 2바이트 크기의 cell pointer array에서만 이루어지기 때문에 훨씬 오버헤드가 적게 듭니다. cell 하나는 테이블일 경우 레코드 하나를 저장하게 되는데 이는 테이블 스키마에 따라 다르지만 크면 몇백바이트 이상이 될 수도 있습니다. 이런 크기의 cell들을 그때그때 정렬한다면 DB를 제대로 쓸 수 없겠죠.
그런데, 정렬이 되어 있지 않다 하더라도 cell content 영역에서 삭제가 일어나거나 업데이트가 일어나면 중간중간에 빈 공간이 생길 수 밖에 없겠죠. 즉, 위의 그림처럼 딱 맞게 content가 씌어진 상태가 되지는 않습니다.
뭐 빈 공간이 생기면 그때마다 앞에서 content를 밀어주면 되긴 하지만 그건 좀 비효율적이고 SQLite는 그래서 Unallocated space가 아닌, cell content 중간에 생기는 free space에 대해서는 관리를 따로 하고 있습니다.
일단 4바이트보다 큰 공간이 생기면 이는 free block이라고 하여 링크드 리스트로 관리됩니다. 위에 기술했던 페이지 헤더의 두번째 필드를 보시면 '첫번째 free block의 offset'이라고 되어 있습니다. free block이 처음 생기면 바로 이 필드에 그 시작 바이트 옵셋을 기록합니다. 그리고 free block의 처음 두 바이트는 또 다음 free block의 바이트 옵셋을 기록하고, 그 다음 두 바이트는 free block의 크기를 기록합니다.
그럼 4바이트보다 작은 free space가 생기면? 이는 따로 정보를 갖고 있지는 않고, 단지 페이지 헤더의 다섯번째 필드인 '조각난 free byte 크기'부분에 그 크기를 합산합니다.
그럼 이제 cell content가 자주 삽입 삭제가 일어난 후의 상황에서 10바이트의 cell을 써넣으라는 호출이 왔다고 가정하겠습니다. SQLite는 제일 먼저 page의 전체 free space의 크기와 cell의 크기를 비교해야겠죠. 일단 cell의 크기가 작다고 가정을 하겠습니다.
그러면 그 다음으로는 unallocated space의 크기와 cell을 비교합니다. 만약 cell이 더 크면? 빈 공간들이 cell content 영역에 산재되어 있다는 의미이므로 이를 모으는 defragment 작업부터 하고서(cell들을 밀어서 영역내의 빈 공간의 파편들을 없앱니다) 공간을 할당해 줍니다.
그렇지 않을 경우는 free block의 링크드 리스트를 뒤져 적합한 크기의 block을 먼저 찾아보고 있으면 그 block의 부분을 쓰도록 하며, 아니라면 역시 defragment를 하게 됩니다.
defragmentPage 소스를 한 번 살펴보겠습니다. 중요치 않은 부분의 코드는 삭제했으므로 원본의 소스와 다를 수 있습니다(3.6.2 버전의 btree.c를 참고하세요).
다음은 실제로 페이지 내에서 빈 공간을 확보하는 allocateSpace()의 코드입니다.
대충 여기까지 보셨으면 dara[hdr+n]이 페이지 헤더의 필드들을 의미한다는 것을 아셔야 됩니다.
get2byte(data[hdr+1])은 첫번째 free block 옵셋을 읽어들이는 것이고 get2byte(data[hdr+5])는 cell content 영역의 시작 옵셋을 읽어들이는 거지요.
디스크의 페이지를 메모리로 읽어들여서 그대로 data[]에 저장한 것이기 때문에 일반적인 방법인 구조체를 이용하여 정보를 읽어들이지 않는 것입니다.
이제 위의 두 함수와 연계하여 대망의 -_- 실제 cell insert코드를 보겠습니다.
insertCell() 함수의 일부입니다.
실제 insert 과정은 이것보다 조금 더 복잡하긴 합니다. Overflow Page와 관련된 부분들도 있고 실제 SQL문에서부터 여기까지 이르기에는 또다른 많은 험난한 과정들이 필요합니다 -_-;
하지만 실제 페이지에 insert 되는 과정을 살펴 보았으므로 보시는 분들은 페이지 구조에 대해서는 이제 충분히 감을 잡으셨으리라 생각됩니다. 그러므로 굳이 delete하는 부분은 볼 필요는 없겠죠. 궁금하면 소스를 뒤져보시길...-_-;
대신 다음에는 실제 cell의 포맷은 어떻게 구성되는지, 어떻게 레코드가 하나의 cell로 뭉뚱그려지는지 -_- 등에 대해 살펴보도록 하겠습니다.
