def search(x, k):
    """
    搜索B+Tree
    :param x: 根结点
    :param k: 关键字
    :return: (目标结点, 目标关键字索引)
    """
    # 定位k的位置索引
    i = x.n - 1
    while i >= 0 and k < x.keys[i]:
        i -= 1

    if i < 0:
        # 如果k小于树的最小值，关键字不存在
        return None, -1

    if x.is_leaf:
        # 如果是叶子结点，直接定位关键字
        if k == x.keys[i]:
            return x, i
        else:
            return None, -1

    # 递归搜索
    return search(x.c[i], k)