MySQL索引为B+树而不用其它的数据结构

可作为索引数据结构的可分为以下几种,依次分析:

  1. Hash结构:对每一条数据求得对应的Hash值填入对应位置。查找时可根据Hash值快速定位。单个查找时间复杂度为O(1)。但是面对范围查找时,仍需要一个一个定位,效果欠佳
  2. 二叉搜索树:在最坏的情况下(数据都小于或大于根节点),会退化成链表,时间复杂度变为O(n)
  3. 平衡二叉树(AVL树):左右子树高度相差不超过一,在进行范围查找时,查找到边界值后会通过回旋查找其他节点。而且当数据库中数据量很大时,会导致树的深度过大,增多了I/O操作。
  4. 红黑树:不能使用红黑树作为索引的原因和平衡二叉树差不多。可以将红黑树理解为一个不太严格的AVL树

红黑树的特点:
1.具有二叉树的特点
2.根节点为黑色
3.叶子节点均为空(NIL)的黑色节点
4.两个红色节点不能相邻,红色节点之间需要被黑色的节点隔开
5.对于每个节点,从它自身出发到达叶子节点多经过的黑色节点数目相同

关于红黑树的问题:为什么有了平衡二叉树还需要红黑树?
平衡二叉树对与树的要求过于严格,这也就导致每一次的增加删除数据都大概率会破坏树的平很结构,从而需要重新进行调整。所以在增删特别频繁的场景下,AVL树会在调整树的结构上花费大量时间,影响性能。也就有了红黑树,它在增删操作下不会像AVL一样频繁破坏规则,调整结构。

  1. B-树:
    B树和B-树是一个东西,英语中是B-Tree。导致了不同翻译版本

每一个节点中会存在k个key值,和k+1个指针,以及key值对应的数据(data)。
节点上的key值按照递增顺序排列,时间复杂度为O(lOGd(N))。在范围查找时,仍存在通过回旋查找其余指的情况。

  1. B+树:
    只有叶子节点中会存储数据,非叶子节点中只存有k个key值与k个指针。这样做的好处是,由于腾出了data的存储空间。增加了每个非叶子节点中能存放的key值与指针数量,B树查找的时间复杂度为logdN,可见越大,性能越好,而d的上限正是由key和指针的个数决定的。另外在Mysql的搜索引擎的索引中在传统的B+树的底层叶子节点之间加上了链表结构,是范围查找更加高效(找到边界节点,便可依次查找剩余节点)。而且数据库的设计者巧妙地利用磁盘预读的特点,将一个节点的大小设置为一页的大小。这样通过一次IO操作就可以将一个节点的数据都读入。(页是计算机管理存储器的逻辑块,硬件及操作系统将内存和磁盘分为大小相等的连续逻辑块,成为页,通常为4k)

为什么可以通过I/O读写次数的多少判断索引的好坏

一般来说,索引文件自身也很大,所以不可能全存储在主存中,往往以索引文件的形式存储在磁盘上。对索引文件的查询就对应这一次IO操作,而读取磁盘上的数据又涉及到寻道时间,旋转时间等,相比于主存,要高几个数量级。所以把IO次数的多少作为一个判定标准

MySQL两大搜索引擎MyISAM和InnoDB对索引的实现方式的不同

这两个引擎都是采用B+树结构。
MyISAM:叶子节点中存放的是对应数据行的物理地址。所以说它的主键索引和辅助索引结构类似,属于非聚集索引。
InnoDB:叶子节点中存的是完整的数据信息。数据文件本身就是主索引,主索引的key值就是主键。
他的辅助索引data域中存放的是主键,找到主键后再到主索引中找到所需数据

索引的优化

关于最左前缀匹配:在使用联合索引时,有下面几种情况不能会导致一些索引属性用不到:范围索引之后的条件、未提供第一个索引对应的条件、中间条件没有提供,只能用到第一个索引条件、查询中有函数
不建议建索引的情况:数据量较小,以2000作为一个划分点;选择性小(索引值基数与记录数的比值)的不建议建索引,相应的优化方法:索引前缀。
主键的选择:与业务无关的自增主键,

Q.E.D.