文章来源s默心的编程开发笔记​​​​​​​为什么要使用索引这个问题比较宽泛要回答这个问题我们先来对查询数据的方式做个调研我们先试试用最简单的方式来实现数据查询它便是全表扫描即将整张表的数据全部或者分批次加载到内存当中。存储的最小单位是块或者页它们是由多行数据来组成的。然后我们将这些块都加载进内存然后逐个块或者页去轮询找到我们要的目标并返回这种方式普遍被认为是会非常的慢的。那它在所有的情况下都这么慢吗实际上存在即合理它也有很适用的地方。当你只有少量的数据比如说十几十行左右那么直接加载到内存里进行全表扫描肯定比我们后面要说的通过索引查询的方式要快当然要在数据量很大的表里进行查询的话该方法显然不适用了因此这里就引出了我们答案。很多情况下我们都要避免全表扫描的情况发生。所以我们的数据库得引入一种更高效的机制这便是索引。它的灵感来自于字典。在字典里面只要我们把一些关键信息组织起来比如说偏旁部首这些查询的时候依据这些信息的指引就能够查到我们想要的页面很快便能定位到我们要查的字了。而这些关键信息以及查找数据的方式便组成了我们的索引。通过索引来大幅提升查询速度便是问题的答案。当然这样刚刚去回答并不会令面试官满意因此你需要看看接下来后续有关索引的知识理解后用自己的方式去作答这样别人才会觉得你对这块是真正的了解了。数据记录中有什么信息能成为索引我们通过之前的内容可想而知自然是能把该记录限定在一定查找范围内的字段就是我们的之前的说的关键信息我们的主键便是一个很好的索引切入点。当然其他键位包括唯一键普通键等也可以作为索引我们将会在接下来的内容中对他们做仔细讲解。现在有了关键字还不行关键是需要让它以什么样的逻辑结构组织起来才能让我们检索的更高效。我们现在来分析索引的数据结构。我们这里就要想一些让查询变得高效的数据结构了最简单的便是二叉查找树复杂点的是它的变种平衡2叉树红黑树以及 B树还有 B树我们的 mysql 数据库索引最终主要是通过 B 树 来实现的。当然还有哈希结构那为了使大家对索引的印象更为深刻接下来我们将各种数据结构用在我们的索引上以体验其优势和劣势之后再更为详细的回答这一个问题索引数据结构二叉查找树之所以引入二叉查找树的知识只是为了让大家对索引的数据结构有一个深刻的印象因此我们将通过图的演示去讲解。众所周知二叉查找树是每个节点最多有两个子树的树结构通常子树被称作左子树或者右子树。二叉查找树的重要性质对于树中的每一个节点 X 它的左子树节点的值均小于节点X的值它的右子树的值均大于节点X的值。以上图根节点为例根节点的值为5它的左子树节点的值均小于5它的右子树节点的值均大于5。如果用二叉查找树来作为我们的索引确实能够提升查询效率。这里需要大家注意的是我们说的索引的存储块和我们之前说的数据库的最小存储单位块或者页实际上并非一一对应只是为了方便我们的理解先将其一一对应起来了。每个存储块存储的是关键字还有指向子树的指针。像上图这棵树它不仅仅是2叉树还是平衡2叉树。平衡2叉树它的任意一个节点的左子树和右子树高度差均不超过1。那这里我们从根部开始根部的左子树比根部的右子树它的高度要差1右子树比较高一些。二叉查找树的查找用的是2分查找比如说我们要搜6那这里6要比5要大因此我们就要从右孩子去查找右子树的根节点是7因为6比7小因此我们又会去查7的左孩子这样子我们就能定位到6了因为是对半搜索所以它的时间复杂度是O(logn)因此其查询效率是非常高的。但是它也有缺点首先咱们数据库的数据可能面临着增加和删除假设我们经过数据的删除之后节点2还有节点6都被删除了。同时我们新增关键词为11和13的节点那根据二叉查找树的特性那它最终就会也变成如下图所示的样子这样就变成了一个线性的2叉树了此时它的查询时间复杂度就变成了O(n)大大降低了查询效率。有的小伙伴会说我们可以利用树的一个旋转的特性来保持这棵树是平衡2叉树这样其时间复杂度会维持O(logn)。这样确实解决了第一个问题但是它还会有第2个问题。咱们之前说影响程序运行速度的瓶颈就是 io 。假如是平衡2叉树的情况下如果我们假定这些索引块都在磁盘中去找6会先发生一次 io 将根的数据读入到我们的内存当中之后再发生一次 io 将7读入进来紧接着又发生一次 io 读入了6。每增加1层高度就会发生一次 io 咱们的平衡2叉树也好红黑树也罢每个节点最多只能有两个孩子而数据块会非常的多因此为了组织起这些数据块树的深度就会很深io 的次数也会很多。如果数据一多其检索性能比之前说的全表扫描要慢很多根本就没法满足我们的优化查询的需求。那还有什么办法能够既降低查询的时间复杂度又降低 io 的次数方法主要就是第1让树变得矮一些第2每个节点能存储的数据多一些这个时候咱们就想到 B 树了