为什么 MySQL 选择 B＋树作为存储引擎索引结构( 七 )

排序、范围查找
的话。那就得把磁盘上的所有记录都加载到内存中，然后再挨个挨个遍历判断，最后过滤出来满足条件的记录返回用户。这种方式能实现功能，但显然效率太低了。同时磁盘上存储的数据可能都远远超过内存大小了，所以这种方式根本就不可取。
那有没有办法解决该问题呢？
我们做一点假设：
假设我们写磁盘的时候能保证顺序写的同时，写入的数据是有序的
。比如，我们写入了三条数据，这三条数据本身写入的时候是排好序的，那么此时范围查找时，我们只要定位到第一条数据，后面的数据是有序的，就可以很快进行按序读取了。如果假设条件成立的话，那排序、范围查找这个问题就从根本上得到简化了。我们也就不用这么大费周折了。我们先基于这个简单假设来看一下，在假设条件成立的情况下，我们还需要解决哪些问题呢？
在这种模式下，我们访问每条记录同时还是需要保留之前的结论：
每条数据都维护一个索引项：offset、size
。

本文插图
我们要存储的是千万级量级的数据，每一条记录都需要一个索引项，那么千万条的记录就需要维护千万条索引项。问题就接着产生了，这千万条的索引项怎么组织？选哪种数据结构组织? 存哪里？...
针对千万条索引项这个问题，我们来看看这个问题有没有解。直观的想法可能就分为两大类：
能否减少索引项的个数？索引项个数减少，自然问题就好解决了
不能减少索引项个数的情况下，是否可以找到
合理的数据结构
来组织。这儿的“合理”可以理解成：空间压缩、优化等等。
我们先从按照第一个思路来看看吧！
Q:为什么会产生千万条索引项呢？
W:因为每一条记录都需要维护一个索引项，我们需要保存千万条记录，所以就得存储千万条索引项。
Q:为什么每一条记录需要维护一个索引项呢？
W:因为每一条记录都是从用户请求传递进来的，每条记录在按照行格式扁平化存储时，长度是不固定的，所以需要每一条记录维护一个索引项。
到这儿我们知道了问题的核心原因了。
到这儿我们将上面层层推导的内容用一张图来总结一下：

本文插图
3.4 索引矛盾点
索引核心矛盾点:
根据前面的分析，每条记录是
变长
的，所以需要每条记录都维护一个索引项。
变长、变长、变长
，我们能从变长这个维度切入做一些改进或者优化吗？既然每条记录的长度我们无法控制，那是否可以将磁盘转化一下呢？