用图文演示Mysql的索引原理

　　

本篇文章给大家主要讲的是关于用图文演示Mysql的索引原理的内容,感兴趣的话就一起来看看这篇文章吧,相信看完用图文演示Mysql的索引原理对大家多少有点参考价值吧。

一、数据结构中常见的索引

【对这块数据结构了解的同学建议跳过本节】

1。二叉树

说起二叉树,我们都知道每个结点最多只能有两个子结点,例如:
用图文演示Mysql的索引原理”> <br/>可以发现二叉树很有规律,左子结点小于当前结点,右子结点大于当前结点。那这样不是查询起来很方便呢?二叉树的性质决定了它的时间复杂度为Olog (n),当然,二叉树的时间复杂度与它的插入顺序有着,如果按升序或降序的方式插入数据,那么它的二叉树的高度h就与结点个数相等了,此时复杂度就提高到了O (n)。</p> <p>假如,数据库使用二叉树来做索引,此时需要插入1000条数据,我们来计算一下这树的高度。(深度为k的二叉树最少有k个结点,最多有2 ^ k - 1个结点)</p> <pre> 2 ^ 10 - 1≈1000,,此时树的高度约为10 　　最差的情况,树的高度为1000 </pre> <p>树的高度决定了查询的效率,而二叉树又会存在高度10 ~ 1000这么大的差距,很明显它已经不适合做我们的索引了! </p> <h4> 2。平衡树</h4> <p>前面把问题摆出来了,二叉树的高度很不稳定,那我们能不能把高度稳定一下呢?这就是平衡树,它会根据插入的情况,动态的调整二叉树的高度(左右子树的高度最多差1),比如:我们插入从10日,9日,8、1 <br/> <img src=

插入或删除元素时,也是需要维护红黑树结构的,之所以索引也不使用红黑树主要是二叉树保存大量结点的时候,会导致树的高度不断增加,比如1亿个节点,树的高度就会达到27层左右,而一般索引又是保存到磁盘中的,如果每次查询都需要一次IO的话,那也就是需要27次IO操作,而每次IO操作都是非常耗时的。

4。B树

平衡树,红黑树都是二叉树,当二叉树保存大量元素的时候会导致树的高度不断增高,那可不可以使用多叉树呢?
用图文演示Mysql的索引原理”> <br/>先来看下B树的定义:</p> <pre> 1, B树的组成 　　,,关键字(可以理解为数据) 　　,,指向孩子节点的指针</pre> <p> <img src= 

 2, B树的性质:
　　*若根结点不是终端结点,则至少有2棵子树
　　*除根节点以外的所有非叶结点至少有M/2棵子树,至多有M个子树(关键字数为子树减一)
　　*所有的叶子结点都位于同一层
用图文演示Mysql的索引原理