MySQL 6种索引数据结构详解:BTree、B+Tree、红黑树、平衡二叉树、二叉树、Hash
2023-02-18 16:38:05 时间
B站搜索“乐哥聊编程“有本篇文章配套视频 https://www.bilibili.com/video/BV1ZV4y1g7hT
二叉树
- 对半搜索,每个节点最多两个孩子
- 左侧孩子小于根节点,右侧孩子大于等于根节点
- 二叉排序树的查找性能在0(Log2n)到O(n)之间
正常情况下长这样
极端情况下长这样
如果长这样的,查找时间复杂度就是O(n)了,那么就得靠平衡二叉树优化了,现在有请平衡二叉树登场...
平衡二叉树
- 满足二叉树
- 任何节点的两个子树的高度最大差为1
- 如果对平衡二叉树进行删除和新增,那么会破坏平衡,就会出发旋转,最终达到平衡,也成自平衡二叉树
虽然能做到平衡了,避免了O(n),但是每次都进行频繁的左旋或右旋,咱也扛不住啊,所以来试试红黑树
红黑树
- 也是自平衡(但没有高度差为1的限制,它有另外一套规则)
- 每个结点是红的或者黑的
- 根结点是黑的
- 每个叶子结点是黑的(NULL)
- 树中不存在两个相邻的红色结点(即红色结点的父结点和孩子结点均不能是红色)
- 从根结点到其任何后代 NULL 结点(默认是黑色的)的每条路径都具有相同数量的黑色结点。
这一点比较难懂:从任意一个结点(包括根结点)到其任何后代 NULL 结点(默认是黑色的)的每条路径都具有相同数量的黑色结点。没听懂?
解释下:这里每个叶子结点(2,4,6,55)都有一个黑色的NULL节点,那么从根节点003到任意的null节点都会经过相同个数的黑色节点(包括黑色的null节点),这样懂了吧。
Hash
- 对索引的key进行一次hash计算就可以定位出数据存储的位置
- 很多时候Hash索引要比B+ 树索引更高效
- 仅能满足 “=”,“IN”,不支持范围查询
- hash冲突问题
B-Tree
- 叶节点具有相同的深度,叶节点的指针为空;
- 所有索引元素不重复;
- 节点中的数据索引从左到右递增排列;
- 数据节点存在每个节点上
B+ Tree
- 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用双向指针连接,提高区间访问的性能
相关文章
- Springboot 整合redis 多数据源 数据库切换
- Oracle PL/SQL例8:标识符引用
- Oracle PL/SQL例9:为变量赋值
- Oracle PL/SQL例10:表达式
- Oracle DB Link问题诊断时候的10046 Trace收集方法
- TDSQL-C 并行查询探索 | DTCC 2022
- docker高级篇1-dockeran安装mysql主从复制
- 直连别人的数据库,靠谱吗
- mysql总结
- MySQL——insert注意事项
- MySQL ——select语句 一条龙服务
- IDEA连接mysql保姆级教学
- MySQL 崩溃恢复过程分析
- MySQL 8.0 数据字典表
- MySQL 连接怎么保活?
- MySQL 不相关子查询怎么执行?
- 学生数据库管理系统
- SpringDataJpa 用MySQL语句怎么分页,spring全家桶SpringDataJpa 用MySQL语句怎么分页
- Docker创建MySQL容器模板命令
- Elasticsearch对应MySQL的对应关系