B+ 트리 갱신

# B+ 트리 갱신 : 삽입
- 검색키 값이 어느 단말노드에 있어야 하는지 찾음
- 단말노드에 인덱스 엔트리를 삽입  검색키의 순서 유지
- 단말노드가 가득 차있으면(검색 키 값이 n개) -> 단말노드 분할(split)
- 내부노드 수정(공간 없으면 내부 노드 분할, 루트 노드 수정(맨 앞 값이 루트 노드로 kim))
- 새로운 노드에서 가장 작은 검색 키 값을 단말 노드의 부모에 삽입

 

# B+ 트리 갱신 : 삭제
- 삭제될 엔트리를 포함하고 있는 단말노드를 찾음
- 동일한 검색키 값을 가지는 엔트리가 있을 경우 => 삭제 레코드를 가리키는 엔트리를 찾을 때까지 검색 후 해당 엔트리 제거
- 자리 있으면 옆의 노드와 병합
- 노드가 너무 작아지면([n/2] 포인터보다 작아짐) 결합
- 노드의 첫 번째 값으로 내부 노드 수정
- 부모의 오른쪽이 내려가고(Mozart) 옆의 제일 오른쪽이 올라감(Gold)

 

 

# B+ 트리 갱신의 복잡도
- 삽입, 삭제 과정은 복잡하지만 최악의 경우보다 적은 디스크 입출력 요구
- 최악의 경우 log [n/2] (N) 
- n: 노드 안에 있는 포인터 최대 개수
- N: 인덱스된 파일의 레코드 개수
- 트리의 높이  높은 성능  대부분의 DBMS들이 인덱스를 구성할 때 선택
- 예 : fanout 100
- 단말노드의 부모는 단말노드보다 100배의 접근성을 가짐
- 비단말노드의 개수는 단말노드의 1/100에 그침
- 주기억장치의 크기가 증가하면 대부분의 비단말노드들이 데이터베이스 버퍼에 있을 가능성이 높음  실제로는 1~2회 디스크 입출력 발생
- 갱신에 따른 노드 분할 가능성은 매우 적음
- 예 : fanout 100 => 한 노드에 50번 ~ 100번을 삽입하여야 분할이 발생함
- 한 번의 삽입은 갱신된 블록을 디스크에 쓰기 위해 1회 정도의 디스크 연산 발생
- 노드 채움
- 임의로 입력 => 2/3 정도 채워짐
- 정렬된 순서로 삽입 => ½ 채워짐