정글 5주차 드디어 본격적인 팀 프로젝트를 시작하게 되었다. 알고리즘 주차의 마지막 주는 b트리와 b+트리를 C언어로 구현하며 진행되었다. 처음 써보는 C언어로 b, b+트리의 복잡한 분기들을 구현하기가 까다로웠지만 무한 디버그 지옥에서 살아남을 수 있었고, 공부한 개념을 정리해 보려고 한다.
B-트리
b트리는 간단하게 말하자면 완전 이진 트리와 이진 검색 트리의 확장판이라고 할 수 있다. 완전 이진 트리는 어떠한 경우라도 균형잡힌 이진 트리를 유지하는 성질을 가졌다. 반면, 이진 검색 트리는 완전 이진 트리를 만족하진 않을지라도 자식 노드들이 부모 노드의 좌우로 크기에 따라 정렬이 된다. b트리는 각 노드와 노드의 키들이 정렬이 되어 있으며, 동시에 완전히 균형잡힌 트리를 유지하는 성질도 갖고있다.
이진 트리를 사용하는 이유는 log2n의 검색 시간을 보장하기 때문이다. b트리 또한 마찬가지다. 오히려 같은 키를 가지고 있어도 더 낮은 높이를 가져 logtn의 시간을 보장하기 때문에 이진 트리보다 더 효율적인 검색 시간을 제공할 수 있다. 이 때문에 많은 데이터베이스에서 정보를 저장하는 데 B-트리를 사용한다.
디스크에서의 B-트리의 활용
일반적인 디스크 구조는 원판위에 데이터를 읽을 수 있는 동심원 형태의 트랙(track)이 있다. 또한, 원판은 마치 파이처럼 섹터(sector)로 구분되어 있어 이 둘의 인덱스가 교차하는 블럭(block)의 데이터에 접근할 수 있다. 각 블럭이 512byte의 메모리 공간을 갖고 있다면, 이 블록들은 또다시 1byte의 공간인 offset으로 나눠진다.
디스크가 회전하며 디스크의 섹터가 변하고, 암(arm)이 움직이며 데이터를 읽어올 트랙의 위치를 바꾼다. 이를 통해 읽어온 데이터는 메인메모리(RAM)에 전달된다. 이 일련의 과정이 DBMS이며, 이를 위해 자료구조가 사용된다.
100개의 데이터가 있고, 각 데이터의 크기가 128byte라고 하자. 한 블럭에 데이터는 총 4개만 들어갈 수 있다. 모든 데이터는 총 25개의 블록에 저장될 것이다. 이 상태에서 데이터를 읽어오려면 25개의 블럭에 대해 검색을 해야하기 때문에 블럭의 개수에 비례한 시간이 걸릴 것이다.
이제 키와 포인터를 저장해 한 데이터에 접근할 수 있다고 하자. 각 키와 데이터는 10, 6 byte를 차지한다면 키, 포인터 쌍은 16 바이트의 공간을 할당하면 된다. 즉, 한 블럭에 32개의 키, 포인터 쌍을 저장할 수 있고, 4개의 블럭이면 모든 데이터에 접근할 수 있게 되었고, 데이터가 있는 블럭을 포함해 5개의 블럭만 검색하면 된다. 이렇게 index를 통해 데이터에 더 빠르게 접근하는 방법을 dense index라고 한다.
데이터가 더 많아지면 위의 방법으로도 검색에 많은 시간이 필요할 것이다. 만약 1000개의 데이터가 있다고 가정하고, 인덱스를 가리키는 다른 인덱스를 만들어보자. 키, 포인터가 저장된 40개의 블럭의 상위 블럭에 키, 포인터 데이터에 접근하는 또다른 키, 포인터 쌍을 저장한다면 단 두개의 블럭으로 40개의 블럭에 접근할 수 있다. 이를 sparse index라고 한다. 이를 통해 2 + 1 + 1, 총 4번의 블럭에 대한 접근으로 데이터를 읽을 수 있게 되었다.
지금까지 반복적인 index의 활용으로 데이터에 더 쉽고 빠르게 접근할 수 있는 multi-level indexing에 대해 알아보았다. b트리는 multi-level indexing을 위한 자료구조라고 할 수 있다.
B-트리의 구조 및 성질
b트리는 루트를 제외한 노드에서 1개 이상의 키를 갖고, 트리의 균형이 유지되는 2 이상의 자식을 갖는 트리 자료구조이다.
b트리는 다음과 같은 성질을 갖는다.
-
b트리의 자식은 t( t >=2) 개이다. 즉, 최소 차수가 t이다.
-
각 노드에서 키의 개수는 자식의 개수보다 한 개 적다.
-
최대 자식 수(최대 차수)는 2t 개이다.
-
그러므로 노드의 키의 개수의 최소와 최대는 각각 t-1 개, 2t-1 개이다.
-
키들은 오름차순으로 정렬되어 있으며, 키보다 작으면 왼쪽 자식으로, 키보다 크면 오른쪽 자식으로 들어간다.
-
루트 노드는 예외로 리프 노드가 아닐 때, 항상 최소 두개의 자식 노드를 가질 수 있다.
B-트리 구현 시 주의할 점
b트리를 구현하기 위해선 트리 생성, 삽입, 검색, 삭제 기능을 구현해야 한다. 코드 상으론 너무 길어 github 링크로 대체하고, 구현 시 주의할 점만 적도록 하겠다.
- 노드 구조체
노드 구조체에는 해당 노드가 리프인지 아닌지 확인하는 leaf와, key_arrd의 포인터 위치를 나타낼 key_len, child_arr의 포인터 위치를 나타낼 child_len, 키들의 배열 key_arr, 자식 노드를 가리키는 포인터들의 배열 child_arr로 구성된다.
struct Node {
bool leaf;
int key_len;
int child_len;
int* key_arr;
struct Node** child_arr;
}; -
생성
트리 생성은 크게 주의할 점은 없다. 트리를 생성하고 루트 노드를 설정해주면 된다. 각 노드들의 생성시엔 key_len과 child_len을 0으로 초기화 해준다. -
삽입
삽입 시에는 노드의 키의 개수가 최대(2t-1)이면 분할을 한 후 삽입할 위치를 찾아 내려가야 한다. 루트 노드가 가득 찼을 때는 새 노드를 만들어 새로 루트 노드로 지정한 후 빈 노드에 이전의 노드를 자식으로 연결한 뒤 삽입 과정을 계속 진행한다. 여러가지 상황들에 대해 꼼꼼히 분기를 해줘야한다. -
검색
검색 과정도 크게 주의할 점은 없다. 키를 이정표로 다음 자식 노드를 찾아 내려가고 각 노드에선 선형검색을 통해 찾고하는 키를 검색한다. -
삭제
삭제 과정은 삽입과 반대로 삭제를 했을 때 최소 키가 유지되어야 하기 때문에, 각 노드의 키의 개수가 최소보다 한 개 더 많은 상황(t)을 유지해준다. 만약 내려가려는 자식 노드의 키의 개수가 t-1 개이면 옆의 형제 노드에서 당겨오거나, 당겨올 수 없는 상황이라면 형제 노드와 병합을 한다. 삭제 과정도 삽입 과정과 마찬가지로 다양한 상황들에 대해 꼼꼼히 분기해줘야 한다.
B+트리
b+트리는 b트리에서 효율적으로 연속적인 데이터를 읽어올 수 있도록 개선한 자료구조이다. b+트리에선 내부노드의 키들을 통해 데이터에 접근을 할 수 없고, 오직 리프 노드에서만 데이터에 접근할 수 있다. 내부 노드의 키들은 이정표의 역할만 수행한다. 리프 노드에선 키를 통해 데이터로 접근할 수 있고, 각 리프 노드들은 연결리스트로 연결이 되어 옆의 리프 노드들까지 연속적인 선형검색이 가능하다.
B+트리의 구조 및 성질
b+트리는 b트리와 유사한 구조를 갖는다. 차이점은 리프 노드가 연결리스트로 서로 연결이 되어 있고, 최대 두 개의 같은 키 값을 가질 수 있다는 것이다. 내부 노드의 키를 기준으로 오른쪽에 위치하는 방법과 왼쪽에 위치하는 방법이 있는데, 여기선 오른쪽에 위치하는 것을 기준으로 삼겠다.
b+트리의 성질은 b트리와 거의 같으니 다른 점만 적어 보겠다.
-
내부 노드에서 데이터에 접근할 수 없다.
-
리프 노드의 각 키에 대응하는 데이터 포인터가 있다.
-
내부 노드에 키 값이 있지만, 리프 노드에는 없을 수 있다.
-
반대로, 리프 노드에도 키 값이 있지만, 내부 노드에는 없을 수 있다.
B-트리 구현 시 주의할 점
b+트리 역시 구현하기 위해선 트리 생성, 삽입, 검색, 삭제 기능을 구현해야 한다. 마찬가지로 코드는 github 링크로 대체하고, 구현 시 주의할 점만 적도록 하겠다.
-
노드 구조체
노드 구조체에는 해당 노드가 리프인지 아닌지 확인하는 leaf와, key_arrd의 포인터 위치를 나타낼 key_len, ptr_arr의 포인터 위치를 나타낼 ptr_len, 키들의 배열 key_arr, 자식 노드를 가리키는 포인터들의 배열 ptr_arr로 구성된다.b트리와 다르게 리프에서 자식 노드를 가리키는 포인터를 데이터를 가리키는 포인터로 사용할 것이기 때문에 child 대신 ptr이라는 이름을 선택했다. node가 아닌 데이터를 가리키는 포인터이기 때문에 void로 형변환 해서 넣어준 뒤, 읽을 때도 다시 형변환해 읽어 주는 과정이 필요하다.
struct Node {
bool leaf;
int key_len;
int ptr_len;
int* key_arr;
struct node** ptr_arr;
struct Node* next_node;
struct Node* prev_node;
};-
생성
트리 생성은 크게 주의할 점은 없다. 트리를 생성하고 루트 노드를 설정해주면 된다. 각 노드들의 생성시엔 key_len과 child_len을 0으로 초기화 해준다. -
삽입
삽입 시에는 노드의 키의 개수가 최대(2t-1)이면 분할을 한 후 삽입할 위치를 찾아 내려가야 한다. 루트 노드가 가득 찼을 때는 새 노드를 만들어 새로 루트 노드로 지정한 후 빈 노드에 이전의 노드를 자식으로 연결한 뒤 삽입 과정을 계속 진행한다. 리프 노드를 분할을 하는 상황에서 내부 노드에 중복되는 키가 생성된다. -
검색
검색 과정도 크게 주의할 점은 없다. 키를 이정표로 다음 자식 노드를 찾아 내려가고 각 노드에선 선형검색을 통해 찾고하는 키를 검색한다. -
삭제
삭제 과정은 삽입과 반대로 삭제를 했을 때 최소 키가 유지되어야 하기 때문에, 각 노드의 키의 개수가 최소보다 한 개 더 많은 상황(t)을 유지해준다. 만약 내려가려는 자식 노드의 키의 개수가 t-1 개이면 옆의 형제 노드에서 당겨오거나, 당겨올 수 없는 상황이라면 형제 노드와 병합을 한다. 삭제 과정에서 내부 노드의 키를 의도적으로 삭제하지 않고 리프 노드만 삭제를 하기 때문에 b트리 보다 따져야 할 분기가 더 적다. 병합하는 과정에서 내부 노드의 키들이 자연스럽게 삭제된다.
