1. 索引

在没有索引的情况下，是如何精确查找数据的？

• 当数据较少，都在一张页内

1. 假如是以主键为条件查找，那么就是按照上一篇所说的，在页目录中使用二分法找到主键所在的槽，然后在槽中遍历，找到对应的数据。

2. 假如不是以主键为条件查找，那就只能全部遍历，这样速度是非常慢的

• 当数据较多，在多张页中

毕竟一张页只有16KB，所以数据保存在多张页的情况很普遍。所以在精确查找一条数据时，首先要找到所在的页，然后在所在页中找到相关数据。

可见，在没有索引的情况下，面对大量数据，查找的速度是非常慢的。

所以，需要索引。

上面说到，因为没有类似“目录”的东西，所以我们在多张页中查询时只能通过遍历去查找页。那么为什么不建立一个目录呢？

1. 首先，主键必须按照顺序排列，即下一个数据页中的主键必须都大于上一个数据页。假如在插入主键为中间数的新数据时，数据将自动进行位移，页将进行自动的分裂。

2. 给所有的页建立一个目录。页的编号不一定是连续的，因为它们在物理存储上也是不连续的。所以我们需要给所有页建立一个目录，让他们在逻辑上连续。这个目录，就叫索引。

2. B+树索引

上文中，我们为了能够快速查找页，对其建立了索引，并简单地认为其中的目录项在物理上是可以连续存储的。

但是存在两点问题：1. 因为页可能会非常多，如果目录项与页一一对应的话，也会非常多，需要非常多的连续空间才能存储下来。2. 当我们对记录进行增删改查时，页会进行变动，那么相对应的目录项也会频繁变动，这不是很好的设计。

所以，如何才能灵活管理目录项？

可以也用页来存放目录项。存放记录的页和存放目录项的页本质是一样的，除了一些用于区分的额外信息。在存放目录项的页中，也包含页目录，以便使用二分法来快速查找相应的存放记录的页。

当一个存放记录的页写满时，将会申请一个新的页来记录，原理和之前都是一样的。

那么问题来了，因为在物理上也是不连续的，假如存放记录的页很多，那么查询起来也是会拉慢速度的，怎么办？对存放记录的页再进行索引。

image.png

抽象来看，这就是一棵B+树，这就是B+树索引的原理：