B樹系列文章
1. B樹-介紹
2. B樹-查找
3. B樹-插入
4. B樹-洗掉
什么是B樹
B樹（英語：B-tree）是一種自平衡的樹，能夠保持資料有序，
使用B樹這種資料結構，可以在對數時間范圍內完成對資料的查找、插入和洗掉操作，
B樹減少定位記錄時所經歷的中間程序，從而加快存取速度，
因此B樹可應用于資料庫和檔案系統的實作
B樹有什么特性
一棵m階B樹有如下屬性(m >= 2)
- 每一個結點最多有m個子結點
- 每一個非葉子結點（除根結點）最少有 ?m/2? 個子結點
- 如果根結點不是葉子結點，那么它至少有兩個子結點
- 有k個子結點的非葉子結點擁有 k ? 1 個鍵
- 所有的葉子結點都在同一層
- 結點內鍵值有序排列，
- 以父結點中某個鍵作為分隔值，該分隔值與左右兒子結點的鍵值的構成排列也是有序的
下圖是一棵3階B樹，
取該B樹父結點中某個鍵作為分隔值
該分隔值的左兒子結點的鍵值均小于該分隔值，右兒子結點的鍵值均大于該分隔值
圖一 3階B樹
根據B樹的定義及特性，定義B樹結點的基本資料結構，這里多加了一個限制，即鍵不會重復
每個B樹結點都包含了鍵值串列和兒子結點串列，默認鍵值按升序排列// 非并發安全
type BTree struct {
m int // 階數
root *BTreeNode
}
type BTreeNode struct {
isLeaf bool // 是否為葉子結點
keyNum int // key個數
keyList []int // key 有序
leafList []*BTreeNode
}
完整代碼
B樹完整代碼
參考
B-tree
B樹-維基百科
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499864.html
標籤：其他
下一篇：【線性DP】數字三角形