B树-查找

/**
* 查找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)
}