알고리즘 서론 - 18.2 - 5 - B 나뭇잎 결산 점 무 지침

제목:
엽 결점 은 자녀 를 가리 키 는 지침 이 필요 없 기 때문에 같은 크기 의 디스크 페이지 에 대해 서 는 내 결점 과 다른 (더 큰) t 값 을 선택 할 수 있 습 니 다.이 변형 을 처리 하기 위해 B 트 리 의 생 성과 삽입 프로그램 을 어떻게 수정 하 는 지 설명해 주 십시오.
생각:
B 트 리 한 그루 의 도 를 t 로 설정 하면 하나의 결점 은 최대 2 * t - 1 개의 키워드 와 2 * t 개의 지침 을 포함 하고 사용 하 는 크기 는 S = (2 * t - 1) * sizeof (key) + (2 * t) * sizeof (child) 이 며 S 가 변 하지 않 는 상황 에서 child 지침 을 저장 하 는 공간 은 모두 key 로 사용 되 며 최대 s = S / sizeof (key) 개의 키 워드 를 저장 하여 s = (2 * t - 1) + 8 * t / sizeof (key) 를 구 할 수 있 습 니 다.따라서 잎 결점 의 도 t2 = t + 4 * t / sizeof (key).
수정 방법:
엽 결점 이 분 단 된 결점 은 역시 엽 결점 이다. 내 결점 을 생 성 하 는 경 로 는 하나의 결점 이 분 단 된 후에 그 중의 한 키 워드 를 상승 시 켜 얻 을 수 있다. 설령 엽 결점 의 도 t2 가 내 결점 의 도 t 보다 훨씬 크 더 라 도 한 엽 결점 이 몇 개의 내 결점 으로 분 단 될 까 봐 걱정 하지 않 아 도 된다. 그 어떠한 상황 에서 도 하나의 결점 은 두 개의 결점 으로 만 분 단 될 수 있다.대부분의 프로그램 은 바 꿀 필요 가 없다. 차 이 는 (1) 엽 결점 과 내 결점 의 분열 조건 이 다 르 기 때문이다. (2) 분 단 된 후 엽 결점 과 내 결점 이 복제 해 야 하 는 관건 적 인 글자 수가 다르다.
생 성 작업 은 수정 할 필요 가 없 을 것 같 습 니 다.
삽입 작업 은 세 부분 을 수정 해 야 합 니 다.
(1) P270, B - TREE - INSERT (T, k), L2 로 변경

int t2 = t + 4 * t / sizeof(int);
if((r->leaf == 1 && r->n == 2*t2-1) || (r->leaf == 0 && r->n == 2*t-1))

(2) P270, B - TREE - INSERT - NOTFULL (x, k), L13, 변경

int i = x->n, t2 = t + 4 * t / sizeof(int);
if((x->child[i]->leaf == 1 && x->child[i]->n == 2*t2-1) || (x->child[i]->leaf == 0 && x->child[i]->n == 2 * t - 1))

（3）P269，B-TREE-SPLIT-CHILD(x, i, y)
L1 이전에 코드 를 추가 합 니 다.
이후 모든 t 는 t2 로 바 뀌 었 다.
코드:

if(y->leaf == 1)
		t2 = t + t * 4 / sizeof(int);
	else t2 = t;