有序数组
这个就更简单了, 将所有值从小到大排序, 这样查找时, 可以采用二分法, 时间复杂度只有 O(logN)....先从根节点 5 开始找, 比 5 大, 那肯定在右边, 所以找到第二层的 6, 比 6 还大, 找到第三次的 8, 比 8 小, 最后找到第四层的 7, 这样最坏的情况也就数据在树的最后一层, 即平均时间复杂度为...他是一种自平衡的二叉搜索树, 即在插入节点时, 判断整个树是否是平衡的, 如果不平衡, 通过一系列旋转操作来达到平衡的目的, 在更新时维持树的平衡需要的时间复杂度也是 O(logN)....在 MySQL 5.6 之前, 只能从 ID3 开始一个一个的回表, 到主键索引上找出数据行, 再比对字段值....而在 MySQL 5.6 引入了索引下推优化, 即在索引遍历过程中, 对索引中包含的字段先做判断, 先过滤到不符合条件的记录, 避免回表:
无索引下推执行流程:
image.png
有索引下推执行流程