B树-查找

B树系列文章

创新互联是一家专注于成都做网站、网站制作和雅安电信机房的网络公司，有着丰富的建站经验和案例。

1.B树-介绍

2.B树-查找

3.B树-插入

4.B树-删除

查找

假设有一棵3阶B树，如下图所示。

下面说明在该B树中查找52的过程

首先，从根结点出发，根结点有两个键40和70，52在40和70之间，因此查找根结点的第二个儿子结点

接着，查找根结点的第二个儿子结点，该结点的第一个键值为55，52小于55，因此查找52可能在该结点的第一个儿子结点上

此时到达叶子结点，遍历该结点的键值列表，发现52在该键值列表上，说明该B树上有目标键值，搜索结束

到达叶子结点时，如果叶子结点上没有目标键值，说明B树上没有目标键值，搜索结束。

可以看出来，上述都给经历过的每个结点的第一个不小于52的键值标红处理了

这个键值在键值数组的下标刚好是要访问的儿子结点在儿子结点列表里的下标。

这里是查找的代码

/**
* 查找key, 返回key所在结点及下标
* 采用递归的方法
**/
func (bTreeNode*BTreeNode) search(key int) (*BTreeNode, int) {
if bTreeNode.isLeaf || bTreeNode.keyNum == 0 {
return nil, -1
    }

// 找到第一个不比key小的，注意leaf的数量比key数量多1
    idx := 0
    for idx < bTreeNode.keyNum && key > bTreeNode.keyList[idx] { // 这里可以采用二分查找提高效率
        idx++
    }

// 在当前节点找到了key
    if idx < bTreeNode.keyNum && bTreeNode.keyList[idx] == key {
return bTreeNode, idx
    }

// 是叶子结点 则找不到了
    if bTreeNode.leafList[idx].isLeaf {
return nil, -1
    }

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

/** 查找key, 返回key所在结点及下标
* 时间复杂度为O(logn)
**/
func (bTree*BTree) Search(key int) (*BTreeNode, int) {
return bTree.root.search(key)
}

分享标题：B树-查找
URL地址：http://mswzjz.cn/article/dsoicpd.html

网站建设知识

B树-查找

查找

其他资讯