产业气象站|都懂的索引绝技，MySQL性能优化做得好的人( 二 )
答案是可以的 。 观察上面的图 ， 二叉树的叶子节点都是按序排列的 ， 从左到右依次升序排列 ， 如果我们需要找id>5的数据 ， 那我们取出节点为6的节点以及其右子树就可以了 ， 范围查找也算是比较容易实现 。
但是普通的二叉查找树有个致命缺点：极端情况下会退化为线性链表 ， 二分查找也会退化为遍历查找 ， 时间复杂退化为O（N） ， 检索性能急剧下降 。 比如以下这个情况 ， 二叉树已经极度不平衡了 ， 已经退化为链表了 ， 检索速度大大降低 。 此时检索id=7的数据的所需要计算的次数已经变为7了 。
文章图片
在数据库中 ， 数据的自增是一个很常见的形式 ， 比如一个表的主键是id ， 而主键一般默认都是自增的 ， 如果采取二叉树这种数据结构作为索引 ， 那上面介绍到的不平衡状态导致的线性查找的问题必然出现 。 因此 ， 简单的二叉查找树存在不平衡导致的检索性能降低的问题 ， 是不能直接用于实现MySQL底层索引的 。
3、AVL树和红黑树
二叉查找树存在不平衡问题 ， 因此学者提出通过树节点的自动旋转和调整 ， 让二叉树始终保持基本平衡的状态 ， 就能保持二叉查找树的最佳查找性能了 。 基于这种思路的自调整平衡状态的二叉树有AVL树和红黑树 。
首先简单介绍红黑树 ， 这是一颗会自动调整树形态的树结构 ， 比如当二叉树处于一个不平衡状态时 ， 红黑树就会自动左旋右旋节点以及节点变色 ， 调整树的形态 ， 使其保持基本的平衡状态（时间复杂度为O（logn）） ， 也就保证了查找效率不会明显减低 。 比如从1到7升序插入数据节点 ， 如果是普通的二叉查找树则会退化成链表 ， 但是红黑树则会不断调整树的形态 ， 使其保持基本平衡状态 ， 如下图所示 。 下面这个红黑树下查找id=7的所要比较的节点数为4 ， 依然保持二叉树不错的查找效率 。
红黑树拥有不错的平均查找效率 ， 也不存在极端的O(n)情况 ， 那红黑树作为Mysql底层索引实现是否可以呢？其实红黑树也存在一些问题 ， 观察下面这个例子 。
红黑树顺序插入1~7个节点 ， 查找id=7时需要计算的节点数为4 。
文章图片
红黑树顺序插入1~16个节点 ， 查找id=16需要比较的节点数为6次 。 观察一下这个树的形态 ， 是不是当数据是顺序插入时 ， 树的形态一直处于“右倾”的趋势呢？从根本上上看 ， 红黑树并没有完全解决二叉查找树虽然这个“右倾”趋势远没有二叉查找树退化为线性链表那么夸张 ， 但是数据库中的基本主键自增操作 ， 主键一般都是数百万数千万的 ， 如果红黑树存在这种问题 ， 对于查找性能而言也是巨大的消耗 ， 我们数据库不可能忍受这种无意义的等待的 。
文章图片
现在考虑另一种更为严格的自平衡二叉树AVL树 。 因为AVL树是个绝对平衡的二叉树 ， 因此他在调整二叉树的形态上消耗的性能会更多 。
AVL树顺序插入1~7个节点 ， 查找id=7所要比较节点的次数为3 。
文章图片
AVL树顺序插入1~16个节点 ， 查找id=16需要比较的节点数为4 。 从查找效率而言 ， AVL树查找的速度要高于红黑树的查找效率（AVL树是4次比较 ， 红黑树是6次比较） 。 从树的形态看来 ， AVL树不存在红黑树的“右倾”问题 。 也就是说 ， 大量的顺序插入不会导致查询性能的降低 ， 这从根本上解决了红黑树的问题 。
推荐阅读
- 产业气象站|5G基站太耗电！三大运营商正式官宣：将智能化关闭5G基站节约电费
- 产业气象站|他从不打无准备之仗，华为联手哈工大究竟想干啥？依任总性格
- 产业气象站|G是否影响健康？，张朝阳用手机保持30厘米
- 爱集微APP|“芯”势力助推游戏产业发展，芯片成为ChinaJoy的关键词之一
- 产业气象站|电力机器人“小白”上岗巡检
- 产业气象站|苏宁智能宣布五项Biu+共享政策，从生态赋能到生态共享
- 产业气象站|点赞“中国芯里的南大智慧”！华为公司CEO任正非一行访问南京大学
- 产业气象站|花多少钱收购，微软正在谈判收购TikTok美国业务
- 产业气象站|包括王兴，马云创办支付宝的本质不是为了支付，很多人没理解
- 上观新闻|半导体产业如何发展？嘉定举办的这个论坛指明了方向