阅读 111

mysql 索引 逻辑结构

mysql 索引 逻辑结构

二分查找法/折半查找法

伪算法 :

1. 前提,数据需要有序

2. 确定数据中间元素 K

3. 比如目标元素 A与K的大小

    3.1 相等则找到

    3.2  小于时在左区间

    3.3  大于时在右区间

4. 重复以上过程,直到找到或遍历完所有数据

 

优点:比较次数少,查找速度快,总体性能好

缺点:要求数据有序,插入数据困难(因为有序,插入时要先找到位置)

 

二叉树

每个节点最多有两个子树

左节点永远小于右节点

最大层数为树的高度,无层数限制

下面文章有更详细的说明

https://www.jianshu.com/p/bf73c8d50dc2

 

平衡二叉树

当数据量大时,二叉树高度较大,查询复杂度上升,于是有了平衡二叉树,特点如下

左右两个子树的高度差的绝对值不超过1,依旧是二叉树

不满足上述条件时,会通过自旋,达到上述条件,故该二叉树不存在严重的数据倾斜现象,查询最坏/最好的时间复杂度都维持在O(logN)。

详细可参考

https://www.cnblogs.com/zhangbaochong/p/5164994.html


文章分类
后端
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐