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://pwwzsj.com/article/dsoicpd.html