B樹系列文章

創(chuàng)新互聯(lián)是一家專注于成都做網(wǎng)站、網(wǎng)站制作和雅安電信機(jī)房的網(wǎng)絡(luò)公司，有著豐富的建站經(jīng)驗(yàn)和案例。

1.B樹-介紹

2.B樹-查找

3.B樹-插入

4.B樹-刪除

查找

假設(shè)有一棵3階B樹，如下圖所示。

下面說明在該B樹中查找52的過程

首先，從根結(jié)點(diǎn)出發(fā)，根結(jié)點(diǎn)有兩個(gè)鍵40和70，52在40和70之間，因此查找根結(jié)點(diǎn)的第二個(gè)兒子結(jié)點(diǎn)

接著，查找根結(jié)點(diǎn)的第二個(gè)兒子結(jié)點(diǎn)，該結(jié)點(diǎn)的第一個(gè)鍵值為55，52小于55，因此查找52可能在該結(jié)點(diǎn)的第一個(gè)兒子結(jié)點(diǎn)上

此時(shí)到達(dá)葉子結(jié)點(diǎn)，遍歷該結(jié)點(diǎn)的鍵值列表，發(fā)現(xiàn)52在該鍵值列表上，說明該B樹上有目標(biāo)鍵值，搜索結(jié)束

到達(dá)葉子結(jié)點(diǎn)時(shí)，如果葉子結(jié)點(diǎn)上沒有目標(biāo)鍵值，說明B樹上沒有目標(biāo)鍵值，搜索結(jié)束。

可以看出來，上述都給經(jīng)歷過的每個(gè)結(jié)點(diǎn)的第一個(gè)不小于52的鍵值標(biāo)紅處理了

這個(gè) 鍵值在鍵值數(shù)組的 下標(biāo) 剛好是 要訪問的兒子結(jié)點(diǎn) 在兒子結(jié)點(diǎn)列表里 的 下標(biāo)。

這里是查找的代碼

/**
* 查找key, 返回key所在結(jié)點(diǎn)及下標(biāo)
* 采用遞歸的方法
**/
func (bTreeNode*BTreeNode) search(key int) (*BTreeNode, int) {
if bTreeNode.isLeaf || bTreeNode.keyNum == 0 {
return nil, -1
    }

// 找到第一個(gè)不比key小的，注意leaf的數(shù)量比key數(shù)量多1
    idx := 0
    for idx < bTreeNode.keyNum && key > bTreeNode.keyList[idx] { // 這里可以采用二分查找提高效率
        idx++
    }

// 在當(dāng)前節(jié)點(diǎn)找到了key
    if idx < bTreeNode.keyNum && bTreeNode.keyList[idx] == key {
return bTreeNode, idx
    }

// 是葉子結(jié)點(diǎn) 則找不到了
    if bTreeNode.leafList[idx].isLeaf {
return nil, -1
    }

return bTreeNode.leafList[idx].search(key)
}

/** 查找key, 返回key所在結(jié)點(diǎn)及下標(biāo)
* 時(shí)間復(fù)雜度為O(logn)
**/
func (bTree*BTree) Search(key int) (*BTreeNode, int) {
return bTree.root.search(key)
}