728x90
b*tree
-
[자료구조] B-Tree, B*Tree, B+TreeComputer Science/Data Structure 2023. 2. 28. 23:02
B-Tree 데이터베이스와 파일 시스템에서 사용되는 트리 자료구조의 일종으로, 이진 트리가 자식 노드를 최대 2개만 가질 수 있지만 B-tree는 자식 노드의 개수가 2개 이상인 트리입니다. 또한 노드 내의 데이터가 1개 이상일 수 있습니다. 노드 내 최대 데이터 수가 2개라면 2차 B-Tree, 3개라면 3차 B-Tree 라고 합니다. 하나의 노드에 여러 정보를 담게 되고, 여러 자식을 가질 수 있게 되면서 "차수"라는 개념이 등장합니다. 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부릅니다. 이렇게 하나의 노드에 여러 자료를 배치하게 되면서 이진 트리보다 훨씬 많은 데이터를 효율적으로 저장소에 담을 수 있게 되었습니다. 하드디스크, SSD와 같은 외부 기억장치(비휘발성 메모리..