[데이터베이스&파일처리] B+트리의 구조

* 본 자료는 박영철 교수님의 수업 자료를 토대로 정리되었습니다. 저에겐 저작권이 없으며 공부 용으로 포스팅 된 글임을 밝힙니다. 당연히 펌은 금지입니다.

 

 

 

*<1,z> : key

Root Node : Pr
Internal Node : Pr, Pc
Leaf Node : Ps, Pa, Pe, Pt, Pb
Page Pointer(Tree Pointer) : 하위노드를 가리키는 화살표
Last Child Page Pointer(LCCP) : 화살 표 중 가장 오른쪽(마지막)에 있는 화살표

Root Node Page는 고정된다.
* 노드의 삽입, 삭제를 반복해도 루트페이지는 변하지 않는다. (값은 변한다.)
Leaf Node 가 아닌 노드는 모두 Internal Node 이다.
* 리프 노드만 탐색 값을 가지고 있기 때문에 리프노드 인지, 아닌지가 중요하다. 리프 노드가 아니 노드, 즉 내부 노드들은 모두 구분자만 가지고 있다. (데이터를 저장하는 형식 자체가 다르다.)
Leaf Node 는 Doubley Linked List로 연결 되어 있다.