企业官网建设流程全解析

文章来源：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 树了