索引是为了加速对表中的数据行的检索而创造的一种分散存储的数据结构
mysql的索引是由存储引擎来实现,不同的存储引擎实现方式不同。
一般是存放在磁盘中
我们都知道mysql的索引使用B树来实现的,那么为什么会考虑B树,不考虑其他数据结构呢?
普通的二叉树不是绝对平衡的,会有一个问题,如下图:
它有可能会形成一个链表,这样就失去了二叉树的优势,需要遍历查找,性能查。
平衡二叉树没有普通二叉树可能会形成链表的问题,但是它还有其他的问题。
这里解释下为什么说没有利用好。 1、操作系统磁盘IO的数据交换一次默认是4KB大小,但是我们的节点里面存储的数据远远小于4KB,即我们进行了一次IO但是没有完全利用这次IO的数据交换大小,造成浪费。 2、操作系统磁盘IO具备预读能力,是什么意思呢?比如我们要读取一张20KB大小的jpg图片,我们第一次读了4KB的头内容,操作系统会认为我们可能需要接下来的16KB的剩余内容,所以会一次性把剩余的内容都传输给我们。
这里我选择的是一个3路的平衡查找树。(即一个节点最多可以有3-1=2个元素)
可以看出同样的高度,它比平衡二叉树存储的数据多得多,减少了IO次数,同时每次IO获取的数据也更多,提升了IO效率。
它有以下几个特点:
这里我解释下为什么说B+Trees的查询能力更稳定: B-Trees可能扫秒到第一层就返回,也可能扫秒到最后一层才返回。可能很快也可能很慢。 B+Trees每次都要扫面到最后一层,因此速度更加稳定。