索引为什么能加快检索的速度
很多人回答这个问题时,喜欢用目录作比喻.
的确,当我们查找书中的某些内容时,会先翻目录页,得到目标所在的页数后再翻到该页查看详细内容.索引也是,内节点就是我们的目录页,叶子节点就是详细内容.我们在内节点中获取叶子节点的指针,然后才去查看叶子节点的行数据.
不过,我认为这样的解释还是没有到位的.来看两个例子.
假设我们现在是要查的是历史书,比如说明朝那些事儿,我们想看看崇祯皇帝朱由检的故事,而我们又知道他是明代最后一个皇帝,所以直接从目录的最后往前翻,这样很快就能找到.
但如果现在我们要在一篇诗集里找一首诗呢?比如说,云雀叫了一整天里的一首很出名的从前慢.这时你并不知道它大概会出现在书中的哪个位置,只能从头到尾地去查目录.在数据库里,这个操作叫做全表扫描.
这两种情况有什么区别呢?历史书是按照历史事件的发生顺序,也就是时间顺序来排列的.而诗集大部分的情况下是无序的.
所以,仅有目录是不够的,目录中的内容得按照某种顺序排列,目录才能更好地起作用.
索引的有序性,正是索引能高效运作的重要原因.
针对索引的有序性,还可以做进一步的思考与总结.比如,为什么一张表需要用到多个索引?主键索引和普通索引有什么区别?还有联合索引呢?为什么索引会失效?
通过分析我们可以发现,上述的问题其实都是相通的,其关键就在于有序性.
是否有序,按什么排序,分析了这两点,几乎等于回答了所有关于索引的问题.
为什么一张表需要用到多个索引?因为查询时有多个维度,所以索引也得按多个维度排序.
主键索引?普通索引?联合索引?简单,它们排序的标准不一样呗.
为什么索引会失效?因为既有索引的排序(a,b,c)和查询的排序(a,c)不一样.
索引是否生效?哪个索引起的作用?这类问题会有很多种情况,如果分别去记忆每种情况的现象,很容易混淆开来,因此我个人认为总结一些提纲挈领的规律/原则,会让分析变得更加简单可靠.
叶子节点上存了哪些东西
在介绍B+树索引的结构时,我们提到过这么一句"内节点存的是叶子节点的指针,叶子节点存的是具体数据",后来又补充道"主键索引(的叶子节点)存的是整行数据,普通索引(的叶子节点)仅存索引列和主键".
不过后来我发现,这个介绍还是比较含糊的.某次和别人讨论MVCC时,对方抛出了一个问题:MVCC下的B+树如何实现?追问之下才发现对方以为叶子节点里存的是多版本的数据.
在一棵B+树上同时存储多个版本的数据,这的确是个技术活.
它的难点在哪里呢?假设我们有两个叶子节点,第一个存的是100~200的数据,第二个存的是200~400的数据,其中有一条数据的当前版本值是100,上次更新的值是400;
当我们想查一条400的记录,那么是应该去第一个节点还是第二个节点找呢?显然是第二个.
但是,如果我们想查的是上个版本值为400的记录呢?如果innodb不存储每个版本数据在每个页上的分布情况,那么是无法第一时间就确定该去第一个节点找的.
如何存储这些信息又是个麻烦的问题,因为某一个叶子节点上存的当前版本数据是连续有序的,但是历史版本是离散无序的.在内节点上可以简单用1~200表示某个叶子节点的当前版本数据存储范围,但是要表示历史版本的话,就得全部列举了(1,5,8,33….),这样内节点原先的精简性就不复存在,它实际上已经和叶子节点没有区别(甚至还是多余的),B+树退化成了B-树,并且索引的内容随着数据版本迭代成倍增长,白白消耗许多空间.
所以,如果要在物理上实现多版本数据并存,与其把它们全部挤在一棵树上,倒不如一个版本就新建一个快照?两种方案占用的空间是一样的.
上面所说的显然是笨方法了,前面我们提过了,历史版本的数据是通过undo log计算出来的,叶子节点里只含最新版本的数据.
如果对叶子节点的具体结构不了解的话,结合其MVCC等内容时的确可能会有这种误解.
来看下叶子节点的结构: