数据结构题目61：B-树的查找

题目：T为m阶B-树的根结点指针，k为要找的关键字值，若查找成功，则返回被查找记录的位置；否则，给出查找失败的信息。

解题思路：根据给定的关键字值ki，先在根结点的关键字集合中采用顺序查找方法或者折半查找方法（因为结点中的关键字是按值有序排列的）进行查找。若有k=keyi，则查找成功，根据相应的指针即可取得记录；否则，若ki<keyi(i=1,2,..,n)，则取指针p(i-1)所指结点后重复这个查找过程，直到在某结点中查找成功，或者在查找过程中出现p(i-1)=空（null），查找失败。

具体算法如下：、

function mbsearch(T, k) {
    let i, n, q, p=T
    while ( p!=null ) {
        n = p.keynum    //取得当前结点中关键字的个数
        p.key[n+1] = Maxkey //给第n+1个关键字域赋一个常量Maxkey
        i = 1   //i为关键字值比较的序号，初值为1
        while ( k > p.key[i] ) {    //在当前的关键字集合中进行比较
            i++
        }
        if ( k == p.key[i] ) {
            return (p, i, 1)    //查找成功
        } else {
            q = p   //保存双亲结点的位置
            p = p.ptr[i-1]  //准备查找下一层的一棵子树
        }
    }
    return (q,i,0)  //查找失败
}

性能分析：
由上可知，在B-树中的查找时间取决于以下两个因素：
1.给定关键字值所在结点的层次数，这关系到I/O操作的次数；
2.结点中关键字值的个数。
时间复杂度为O(以2为底的logn)。