julia coding story
B+ Tree 본문
□ B+ tree개념
: 실세계에서 가장 널리 활용되는 B-tree
: 인덱스 구조와 시퀀스셋(데이터셋)으로 구성
: 인덱스 구조의 루트를 제외한 모든 노드들은 at least half full(절반 이상) 조건을 만족함 (단, 초기 상황은 예외)
▶ 인덱스 구조
○ 각 노드가 레코드 대신 (오른쪽으로 갈지, 왼쪽으로 갈지만 알려주는) key 값 만으로 구성된 B-tree
○ 노드의 key 값은 데이터 노드로 찾아가는데 이요하는 navigation에 이용
- 노드의 key 값보다 작거나 같으면 search_key <= node_key 바로 좌측 포인터로 이동
- 노드의 key값보다 크면 search_key>node_key 그 노드의 다음 key 값과 비교
- 만약 다음 key 값이 없으면 그 노드의 맨 우측 포인터로 이동
○ B-tree의 requirements(필요조건)와 constraints(제한)을 만족해야한다.
▶ 시퀀스 셋(data node set)
○ 모든 레코드를 저장
○ 노드들이 연결리스트를 구성함
○ 모든 레코드들은 key 값 순서로 정렬 (asending sort)
□ B+ tree의 장점
1. 인덱스 구조의 노드들은 branching factor를 크게 할 수 있음
• 리프 노드를 제외하고 데이터를 담아주지 않으므로 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있음
• 하나의 노드에 더 많은 key를 담을 수 있으므로 트리의 높이를 낮출 수 있음
=> 빠른 검색이 가능함 (동일한 메모리에 더 많이 담길 수 있음)
2. 풀 스캔시, B+ tree는 리프노드에 데이터가 모두 있으므로 한번의 선형 탐색으로 가능
• B-tree의 경우 모든 노드를 확인해야함
3. 범위 검색(Range Search)이 가능
• 리프 노드끼리 연결리스트로 구성되어 있어 순차적인 범위 탐색에 유리
• B+ tree인덱스는 등가 비교와 범위 검색에 사용 가능
• 범위 검색은 먼저 시작하는 key값을 스캔하여 해당 리프 노드를 찾은 다음 리프 노드만을 따라가면서 검색
ex: 만약 key값이 38~55인 레코드들을 찾고 싶다면 38을 찾은 다음 리프 노드에서 정렬되어 있는 링크를 따라 55까지 검색해주면 됨
□ Insertion of B+ tree : 첫 레코드의 삽입
1. 첫 레코드의 삽입 : 아직 하나의 레코드도 삽입되지 않은 상황 (Root가 NULL인 경우)
• 인덱스 노드를 하나 만들고 이를 루트가 가르키게 함
• 데이터 노드를 하나 만들고 레코드를 넣음
• 루트 인덱스 노드 Pointer[0] (데이터 노드에 대한 포인터)가 이 데이터 노드를 가리키게 함
• 루트 인덱스 노드의 pointer[1]에 NULL을 넣음 => 초기상황 삽입임을 나타냄
if (!ROOT)
{ // 처음으로 하나의 레코드를 삽입하게 된다.
ROOT = (type_ptr_idxnode)malloc(sizeof(type_idx_node));
HEAD = (type_ptr_datanode)malloc(sizeof(type_data_node));
HEAD->rec[0] = in_rec; // data node 에 첫 레코드를 넣음.
HEAD->fill_cnt = 1;
HEAD->link = NULL;
ROOT->ptri[0] = NULL; // 리프노드임을 나타냄.
ROOT->ptrd[0] = HEAD;
ROOT->ptrd[1] = NULL; // 초기상황임을 나타냄.
strcpy(ROOT->key[0], in_rec.name); // 키를 인덱스 노드에 넣음.
ROOT->fill_cnt = 1;
return 1; // 첫 레코드의 넣기 종료.
}
2. Root가 NULL이 아닌 경우 초반부 삽입
• Sequence set에 데이터 노드 하나만 존재하는 경우
• Root 인덱스 노드의 pointer[1]이 NULL인지를 체크하여 확인함
• 초반부 삽입이면 무조건 첫 데이터 노드에 삽입하는 것을 시도 (즉, index 구조에서의 navigation과정을 생략)
2.1) 데이터 노드에 빈자리가 있으면 순서에 맞춰서 삽입 후 종료 (최대 레코드가 변경되었다면, 루트 인덱스 노드의 key[0]도 이것으로 변경)
else if (!ROOT->ptri[0] && !ROOT->ptrd[1])
{ // 초기상황임.
fc = HEAD->fill_cnt;
if (fc < MAXD_data) { // 아직 full 은 아님. 적당한 오름 차순 위치에 넣음.
for (i = 0; i < fc; i++) {
if (strcmp(in_key, HEAD->rec[i].name) < 0)
break; // i 가 결정됨.
else if (strcmp(in_key, HEAD->rec[i].name) == 0) {
//printf("동일키 이미 존재로 삽입 실패! \n");
return 0;
}
else; // try next i.
}
// i 부터 우측을 한칸씩 우측으로 시프트함.
for (j = fc; j > i; j--) HEAD->rec[j] = HEAD->rec[j - 1];
HEAD->rec[i] = in_rec; // 새 레코드를 넣음.
HEAD->fill_cnt++;
strcpy(ROOT->key[0], HEAD->rec[fc].name); // 데이타노드의 마지막 레코드의 키를 부모에게 넣어줌. 여기 중요!!
return 1; // 성공으로 종료.
}
2.2) 데이터 노드에 빈자리가 없다면 데이터 노드 splitting 진행(overflow처리)
• 삽입할 레코드와 데이터 노드의 모든 레코드를 big node에 넣고 두 부분으로 분리
• big node의 중간 레코드까지 첫 부분으로 하여 현재 데이터 노드에 넣고, 뒷 부분은 새로운 데이터 노드를 햘당하여 넣음
• 중간 레코드의 key 값 = 루트 인덱스 노드의 key[0]
• 새로운 데이터 노드(new_ptrd)에 대한 포인터를 루트 인덱스 노드의 pointer[1]에 넣음
• 두 데이터 노드를 연결 : link of data node 1 = pointer to data node 2 / link of data node 2 = NULL
else
{ // 첫 데이타노드가 full 임. split 가 필요함.
// big data node 를 준비함
for (i = 0; i < MAXD_data; i++)
{
if (strcmp(in_key, HEAD->rec[i].name) < 0)
break;
else if (strcmp(in_key, HEAD->rec[i].name) == 0) {
//printf("동일키 이미 존재로 삽입 실패! \n");
return 0;
}
else; // try next i.
}
for (j = 0; j < i; j++) // i 이전 부븐을 빅노드로 가져옴.
bnode_data.rec[j] = HEAD->rec[j];
bnode_data.rec[j] = in_rec;
j++;
while (i < MAXD_data)
{
bnode_data.rec[j] = HEAD->rec[i];
j++; //i와 j를 증가 시킨다.
i++;
}
// index of center record is at D_data. center 및 그 좌측은 노드 HEAD 로 옮긴다.
for (i = 0; i <= D_data; i++)
HEAD->rec[i] = bnode_data.rec[i];
HEAD->fill_cnt = D_data + 1;
new_ptrd = (type_ptr_datanode)malloc(sizeof(type_data_node));
for (i = 0; i < D_data; i++) // 나머지 뒤는 새로운 노드에 넣음.
new_ptrd->rec[i] = bnode_data.rec[i + 1 + D_data];
new_ptrd->fill_cnt = D_data;
strcpy(ROOT->key[0], HEAD->rec[D_data].name); // 앞 데이타노드의 맨 뒤 레코드의 키를 부모에 넣음
ROOT->ptrd[1] = new_ptrd; // 이 작업으로 지금부터 정상적인 B+ 트리가 됨.
HEAD->link = new_ptrd; // 연결리스트에 새 노드를 연결함.
new_ptrd->link = NULL; // 새 데이타 노드가 연결리스트의 마지막 노드임.
return 1; // 성공으로 종료.
}
} // 초기상황 삽입 종료.3. 일반적인 경우
○ 루트 인덱스 노드의 pointer[1]이 NULL인지 아닌지 체크하여 확인
○ Root에서 출발하여 삽입할 레코드가 들어가야 할 데이터 노드를 탐색
• index 구조를 nevigation
• new key <= key in node 비교에 의해 아래로 내려가는 작업을 반복
• 못 찾으면 그 노드의 맨 우측 포인터를 따라 내려감
• 내려가다가 결국 데이터 노드에 도달
// (ROOT가 NULL 이거나 초기상황임)이 아니면 여기로 온다. 즉 B-tree 인덱스는 정상 B-tree 임.
// 먼저 탐색을 통하여 in_rec 이 들어갈 데이타노드를 찾는다.
curr = ROOT; //root의 값을 curr에 넣는다.
// 인덱스 구조 내비게이션.
top = -1; // 스택을 empty 로 초기화한다.
if (ROOT->ptri[0] != NULL) { // ROOT 가 리프노드가 아님.
do {
for (i = 0; i < curr->fill_cnt; i++) { // 자식으로 내려갈 포인터를 찾음.
if (strcmp(in_key, curr->key[i]) <= 0)
break; // 자식으로 내려 가기 위함
}
push(curr); // 나중에 부모를 찾기 위해 저장함.
curr = curr->ptri[i]; // 자식으로 내려 감.
if (curr->ptri[0] == NULL)
break; // 내려 간 새 curr 노드가 리프노드임.
} while (1);
} // 인덱스구조 내비게이션.
// curr 는 인덱스구조의 리프노드임. 여기서는 데이타노드로 내려가야 함.
for (i = 0; i < curr->fill_cnt; i++)
if (strcmp(in_key, curr->key[i]) <= 0)
break;
○ 찾은 데이터 노드에 삽입 시도
• 경우1) 빈 자리가 있는 경우 : 순서에 맞춰 삽입하고 종료
parent = curr; // 리프노드 저장. (주의: 스택에 넣지는 않음.)
curr_d = curr->ptrd[i]; // 데이타노드로 내려 감. curr_d 은 데이타노들 가리킴.
down_idx = i; // 부모에서 자식으로 내려간 인덱스 저장. 나중에 이용할 것임.
// 이 데이타노드(curr_d)에 in_rec 레코드를 넣어야 함.
fc = curr_d->fill_cnt;
if (fc < MAXD_data) // 아직 full 은 아님. 적당한 오름 차순 위치에 넣음.
{
for (i = 0; i < fc; i++) {
if (strcmp(in_key, curr_d->rec[i].name) < 0) break; // i 가 결정됨.
else if (strcmp(in_key, curr_d->rec[i].name) == 0)
{ //printf("동일키 이미 존재로 삽입 실패!\n");
return 0;
}
else; // try next i.
}
// i 부터 우측을 한칸씩 우측으로 시프트함.
for (j = fc; j > i; j--)
curr_d->rec[j] = curr_d->rec[j - 1];
curr_d->rec[i] = in_rec; // 새 레코드를 넣음.
curr_d->fill_cnt++;
if (down_idx < parent->fill_cnt) // 마지막 포인터로 내려 온 경우는 부모에 반영하지 않음.
strcpy(parent->key[down_idx], curr_d->rec[fc].name);// 데이타노드의 마지막 레코드의 키를 부모에게 넣어줌. 여기 중요!!
return 1; // 성공으로 종료.
}• 경우 2) 빈 자리가 없는 경우 : overflow 발생
○ 일반적인 경우 : 경우 2의 overflow 발생
• 삽입할 레코드와 도달한 데이터 노드의 모든 레코드를 big node에 넣고 두 부분으로 분리
• Big node의 중간 레코드 (middle record)까지를 첫 부분으로 하여 도달한 데이터 노드에 넣고, 뒷부분은 새로운 데이터 노드를 할당하여 넣음
• 새로운 데이터 노드에 대한 포인터를 ptr_new_data라 하자.
• middle record의 key를 mid_key라 하자
• <mid_key, ptr_new_data> 쌍을 도달한 데이터 부모 노드에 삽입
else
{ // 첫 데이타노드가 full 임. split 가 필요함. big data node 를 준비함
for (i = 0; i < MAXD_data; i++) {
if (strcmp(in_key, curr_d->rec[i].name) < 0) break;
else if (strcmp(in_key, curr_d->rec[i].name) == 0)
{ //printf("동일키 이미 존재로 삽입 실패!\n");
return 0;
}
else; // try next i.
}
for (j = 0; j < i; j++) // i 이전 부분을 빅노드로 가져옴.
bnode_data.rec[j] = curr_d->rec[j];
bnode_data.rec[j] = in_rec;
j++;
while (i < MAXD_data) {
bnode_data.rec[j] = curr_d->rec[i];
j++; //i와 j를 증가 시킨다.
i++;
}
// center record is at index D_data. center 및 그 좌측은 노드 curr_d 로 옮긴다.
for (i = 0; i <= D_data; i++) curr_d->rec[i] = bnode_data.rec[i];
curr_d->fill_cnt = D_data + 1;
new_ptrd = (type_ptr_datanode)malloc(sizeof(type_data_node));
for (i = 0; i < D_data; i++) // 나머지 뒤는 새로운 노드에 넣음.
new_ptrd->rec[i] = bnode_data.rec[i + 1 + D_data];
new_ptrd->fill_cnt = D_data;
new_ptrd->link = NULL;
// 시퀀스셋 연결리스트에 이 새로운 노드를 curr 다음 노드가 되게 끼워 넣어야 한다.
new_ptrd->link = curr_d->link;
curr_d->link = new_ptrd;
// 쌍 [center키, new_ptrd] 을 인덱스구조의 리프노드인 부모 노드에 넣는 새로운 문제가 생긴다.
// 아래 3 줄로 변수 설정후에 아래의 b-tree 삽입 루프로 간다.
curr = parent;
strcpy(in_key, curr_d->rec[D_data].name); // 쌍의 원소 1.
child_d = new_ptrd; // 쌍의 원소 2.
} // 데이타노드가 full 인 곳에 삽입.
* B-tree에 하나의 쌍을 넣음
// 여기서 부터는 B-tree 에 하나의 쌍을 넣는 작업을 한다.
do {
// 여기에 오기 전에 변수 in_key 에 넣을 키, 변수 child_d 또는 child 에 포인터를 설정하고 온다.
// The pair <in_key, child_d> 또는 <in_key, child> 를 curr 에 넣어야 한다.
// child_d: 데이타노드를 포인트, child: 인덱스노드를 포인트. 둘 중 무엇을 이용할지는 curr의 리프/비리프 여부로 결정.
if (curr->fill_cnt < MAXD_idx) // curr 에 빈자리가 있다. 이 curr 노드에 넣는다.
{
for (i = 0; i < curr->fill_cnt; i++) //i를 curr->fill_cnt까지 증가하면서 조사한다.
if (strcmp(in_key, curr->key[i]) < 0) //i 에서의 키가 in_key 보다 더 크면 멈춘다.
break;
for (j = curr->fill_cnt; j > i; j--) { // i 부터 우측 부분을 포인터와 키를 한칸씩 우로 시프트 한다.
curr->ptrd[j + 1] = curr->ptrd[j];
curr->ptri[j + 1] = curr->ptri[j];
strcpy(curr->key[j], curr->key[j - 1]);
}
strcpy(curr->key[i], in_key); // 키 삽입
if (curr->ptri[0] == NULL) { // curr 는 리프노드이므로 type-1 삽입이다.
curr->ptrd[i + 1] = child_d; // 자식 포인터를 ptrd 에 삽입
curr->ptri[i + 1] = NULL;
}
else { // curr 는 리프노드가 아니다. 고로 type-2 삽입이다. 자식 포인터를 ptri 에 넣는다.
curr->ptri[i + 1] = child;
curr->ptrd[i + 1] = NULL;
}
curr->fill_cnt++; // fill 카운트 증가시킴
return 1; // 삽입 성공으로 종료.
}
else // curr 에 빈자리가 없다. 인덱스노드의 빅노드 이용하여 split & elevation 을 수행한다.
{
for (i = 0; i < MAXD_idx; i++) {
if (strcmp(in_key, curr->key[i]) < 0) // 만약 i 의 키가 in_key가 크면 멈춤
break;
}
bnode_index.ptri[0] = curr->ptri[0]; // 먼저 포인터 0 을 옮김.
bnode_index.ptrd[0] = curr->ptrd[0]; // " "
for (j = 0; j < i; j++) { // i 전까지 curr 의 내용을 옮김.
strcpy(bnode_index.key[j], curr->key[j]);
bnode_index.ptri[j + 1] = curr->ptri[j + 1];
bnode_index.ptrd[j + 1] = curr->ptrd[j + 1];
}
strcpy(bnode_index.key[j], in_key); // 쌍의 첫 원소 in_key 를 넣어 준다.
// 쌍의 원소2 인 포인터를넣어 준다.
if (curr->ptri[0] == NULL) { // curr 는 리프노드이므로 type-1 삽입이다.
bnode_index.ptrd[j + 1] = child_d; // 자식 포인터를 ptrd 에 삽입
bnode_index.ptri[j + 1] = NULL; // 이것은 넣지 않아도 문제는 없다.
}
else { // curr 는 리프노드가 아니다. 고로 type-2 삽입이다. 자식 포인터를 ptri 에 넣는다.
bnode_index.ptri[j + 1] = child;
bnode_index.ptrd[j + 1] = NULL; // 이것은 넣지 않아도 동작은 잘 한다.
}
j++; // j 증가시킴
while (i < MAXD_idx) {
strcpy(bnode_index.key[j], curr->key[i]); //curr의 레코드를 bnode 로 복사
bnode_index.ptri[j + 1] = curr->ptri[i + 1]; // 그 우측의 포인터도 복사.
bnode_index.ptrd[j + 1] = curr->ptrd[i + 1];
j++; //i와 j를 증가 시킨다.
i++;
}
// 빅노드를 반으로 나누어 전반부를 curr 에 넣는다.
for (i = 0; i < D_idx; i++) {
curr->ptri[i] = bnode_index.ptri[i]; //빅노드의 앞의 반을 현재 노드에 넣어준다. [레코드, 포인터]
curr->ptrd[i] = bnode_index.ptrd[i];
strcpy(curr->key[i], bnode_index.key[i]);
}
curr->ptri[i] = bnode_index.ptri[i]; //bnode.ptr[i]는 curr.ptr[i]를 가르킨다.
curr->ptrd[i] = bnode_index.ptrd[i];
curr->fill_cnt = D_idx;
new_ptri = (type_ptr_idxnode)malloc(sizeof(type_idx_node)); // 빅노드의 후반부를 새로운 노드에 넣는다.
for (i = 0; i < D_idx; i++) { //뒤의 반을 새노드에 저장
new_ptri->ptri[i] = bnode_index.ptri[i + 1 + D_idx];
new_ptri->ptrd[i] = bnode_index.ptrd[i + 1 + D_idx];
strcpy(new_ptri->key[i], bnode_index.key[i + 1 + D_idx]);
}
new_ptri->ptri[i] = bnode_index.ptri[MAXD_idx + 1]; // 맨 마지막 포인터를 옮긴다.
new_ptri->ptrd[i] = bnode_index.ptrd[MAXD_idx + 1];
new_ptri->fill_cnt = D_idx;
strcpy(in_key, bnode_index.key[D_idx]); // 빅노드의 중간 키를 elevation 할 키로 함
child = new_ptri; // 새로 할당한 노드의 포인터를 elevation 할 포인터로 함.
if (top >= 0) { // curr의 부모가 있음.
curr = pop(); // curr 의 부모를 스택에서 가져 와서 그것으로 curr 를 변경.
// 새로운 curr 에 쌍 [in_key, child] 을 넣는 작업을 수행할 예정임.
}
else { // curr 가 ROOT 이다. 부모가 없다. 부모를 만들고 그것이 부모가 되어야 한다.
tptr = (type_ptr_idxnode)malloc(sizeof(type_idx_node));
strcpy(tptr->key[0], in_key);
tptr->ptri[0] = curr;
tptr->ptri[1] = child;
tptr->ptrd[0] = NULL;
tptr->fill_cnt = 1;
ROOT = tptr; // 루트를 변경.
return 1; // 삽입 성공으로 종료.
} // else.
} // else.
} while (1);
} //함수 insert_arec_b_plus_tree| 구분 | B-Tree | B+ tree |
| 데이터 저장 | 모든 노드 데이터 저장 가능 | 오직 리프노드에만 데이터 정장 가능 |
| 트리의 높이 | 높음 | 낮음 (한 노드당 key를 더 많이 담을 수 있음) |
| 풀 스캔시 검색 속도 | 모든 노드 탐색 | 리프 노드에서 선형 탐색 |
| 키 중복 | 없음 | 있음 (리프 노드에 모든 데이터가 있으므로) |
| 연결리스트 | 없음 | 리프 노드끼리 연결리스트로 연결 |
'소프트웨어 > Algorithm' 카테고리의 다른 글
| [알고리즘]B-Tree Deletion (0) | 2022.10.15 |
|---|---|
| [알고리즘] B-Tree Insertion (2) | 2022.10.14 |
| [알고리즘] B-Tree Retrieval (0) | 2022.10.14 |
| [알고리즘] B-Tree (0) | 2022.10.04 |
| HashMap의 설명 및 사용방법 (0) | 2022.01.05 |
