B-tree advanced version
B-tree와의 유일한 차이점은 B+ tree가 leaf node에 데이터를 저장한다는 것이다.
Structure
Index
- 각 node가 record 대신 key로 구성
- key들은 search시에 navigation 역할
Sequence set (data node set)
- 모든 record 저장
- node들의 구조는 linked-list
- 모든 record들은 key 값 순서로 정렬됨
Insertion B+ tree
0. (초반부) root가 NULL인 경우
- Index node를 만들고 root가 가리킴
- data node를 만들고 record를 넣음
- root Index node의 P[0]가 data node를 가리킴
- root Index node의 P[1]에 NULL을 넣음
1. (초반부) root가 NULL이 아닌 경우
- Sequence set에 data node가 1개만 존재하는 경우
- root Index node의 P[1]이 NULL인지 체크
1-1) data node에 빈 자리가 있으면 오름차순으로 삽입 후 종료
1-2) data node에 빈 자리가 없으면 data node를 splitting 진행 (overflow)
2. (일반적인 경우)
- root Index node의 P[1]이 NULL인지 체크
- 찾은 데이터 노드에 삽입을 시도
2-1) 빈 자리가 있으면 순서에 맞춰서 삽입 후 종료
2-2) 빈 자리가 없으면 overflow 처리
- 삽입할 record + 찾은 data node의 모든 record를 big node에 넣고 두 부분으로 분리 -> 이부분이 삽입과 다름
- bing node의 중간 record까지를 첫 부분으로 하고 뒷 부분은 새로운 new data node를 할당함
- <mid_key, ptr_new_data>쌍을 찾은 data node의 parent node에 삽입
meme