B-樹

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

B-樹係種數據結構,可以話係二元搜尋樹廣義化

定義[編輯]

睇埋:樹 (抽象資料類型)

定義上,一樖 m-order 嘅 B-樹係一樖樹型數據,並且有以下嘅特性[1]:Ch. 7.12

  • 每粒節點頂攏有 m 粒子節點;
  • 每粒唔係葉(葉節點 = 冇子節點嘅節點)唔係根嘅節點有最少 m/2 咁多粒子節點;
  • 如果根節點唔係葉節點,佢就最少 2 粒子節點;
  • 一粒唔係葉、有 c 粒子節點嘅節點,會帶有 c-1 件 search key,啲 search key 會幫手界定啲子樹嘅值要點分割;
  • 啲葉節點冚唪唥都喺同一層。

好似下圖就係一樖 m = 5 嘅 B-樹。

B-tree.svg

睇埋[編輯]

[編輯]

  1. John Bullinaria, (2019). Lecture Notes for Data Structures and Algorithms (PDF). School of Computer Science, University of Birmingham.