자료구조 알고리즘/이론
B+Tree
내공얌냠
2023. 5. 9. 19:16
- 같은 레벨의 모든 키값들이 정렬됨
- 같은 레벨의 sibling node는 연결리스트 형태로 연결되어있음
- 모든 leaf node는 연결리스트로 연결되어 있음
- 키값 중복 X, 탐색 유리
- 블럭 사이즈를 더 많이 이동할 수 있음(key 값에 대한 하드디스크 주소 X)
- 그러나 무조건 leaf node 까지 내려가야함
- 삽입, 삭제 모두 leaf node에서 이루어짐
- 모든 leaf node는 같은 레벨
- leaf node가 아닌 node의 키 값의 수는 그 노드의 서브트리수-1
단말 노드 <> 비단말 노드
- 인덱스 노드 : leaf node가 아닌 자료, value값에 다음 노드를 가리키는 포인터 주소 존재
- 데이터 노드 : lead node 자료, value값에 데이터가 존재
References
https://ssocoit.tistory.com/217
[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree
위 글을 보고 정리를 하지 않을 수 없었습니다. 가슴이 시키네요;; 그렇다면 바로 B-Tree, B*Tree, B+Tree의 특징에 대해서 알아봅시다. 목차 0. 이진트리 B-Tree, B*Tree, B+Tree에 대해서 알아보자면서 갑자
ssocoit.tistory.com
https://sdesigner.tistory.com/79
B-Tree & B+ Tree 자료구조 알아보기
본 포스팅은 jisikTank 스터디에 참여하며 정리한 문서입니다. jisikTank CS지식 Git Repository B-Tree & B+ Tree 이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면(skewed Tree) 검
sdesigner.tistory.com
728x90
반응형