https://www.cnblogs.com/tiancai/p/9024351.html
    https://blog.csdn.net/beautiful_face/article/details/69942116

    google搜索关键字 “what is the time complexity of xxxx tree”

    平衡二叉树（AVL）
    AVL树的插入删除时间复杂度为O(log n)，搜索时间复杂度为O(n)，优于二叉搜索树和红黑树。

    二叉查找树
    在任何二叉搜索树中，所花费的时间复杂度是O(h)，其中h是树的高度。因为已知树是平衡二叉搜索树，所以在最坏的情况下搜索一个元素是O(logn)。

    红黑树 时间复杂度：logn
    红黑树为插入、搜索和删除提供了对数平均时间复杂度和最坏情况时间复杂度。再平衡的平均时间复杂度为O(1)，最坏情况复杂度为O(log n)。此外，当涉及到批量和并行操作时，红黑树具有有趣的特性。

    B+ tree 时间复杂度：
    除了磁盘读取之外，该算法还对从磁盘读取的每个节点执行线性搜索。每次线性搜索的时间复杂度为O(t)。因此，B+-树搜索操作的总时间复杂度为O(t logn)。

    B- tree 时间复杂度：
    b -树从根开始生长和收缩，这与二叉搜索树不同。二叉搜索树向下生长，也从向下收缩。和其他平衡二叉搜索树一样，搜索、插入和删除的时间复杂度是O(log n)。