B-樹 是一種多路搜尋樹（並不是二叉的），一顆m階的B-樹，或為空樹，或者： 1.定義任意非葉子結點最多隻有M個兒子；且M>2； 2.根結點的兒子數為[2, M]； 3.除根結點以外的非葉子結點的兒子數為[M/2, M]； 4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字） 5.非葉子結點的關鍵字個數=指向兒子的指標個數-1； 6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i]

B-樹

是一種多路搜尋樹（並不是二叉的），一顆m階的B-樹，或為空樹，或者：

1.定義任意非葉子結點最多隻有M個兒子；且M>2；

2.根結點的兒子數為[2, M]；

3.除根結點以外的非葉子結點的兒子數為[M/2, M]；

4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）

5.非葉子結點的關鍵字個數=指向兒子的指標個數-1；

6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i]

7.非葉子結點的指標：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小於K[1]的子樹，P[M]指向關鍵字大於K[M-1]的子樹，其它P[i]指向關鍵字屬於(K[i-1], K[i])的子樹；

8.所有葉子結點位於同一層；

B+樹

B+樹是B-樹的變體，也是一種多路搜尋樹：

1.其定義基本與B-樹同，除了：

2.非葉子結點的子樹指標與關鍵字個數相同；

3.非葉子結點的子樹指標P[i]，指向關鍵字值屬於[K[i], K[i+1])的子樹（B-樹是開區間）；

5.為所有葉子結點增加一個鏈指標；

6.所有關鍵字都在葉子結點出現；