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

在内存中都可以实现，我们如何选择呢？直观来看我们选哪种好像都可以，但我们别忘了，我们的数据最终要落到硬盘，既然这儿得不出结论，那我们就从硬盘的维度来看看，硬盘上哪种数据结构好维护呢？
3.2 目光转向磁盘
根据前面的介绍，我们的数据流向分为三个阶段，以读取操作举例：
磁盘->内存->用户
。既然这样的话，我们的
直观想法是，如果能在内存和硬盘这两种介质上维护同一种数据结构
，那就最完美了，这样当用户请求进来后，从磁盘加载数据后，可以直接加载到内存中，然后做一些处理就返回用户了。如果直观想法走不通的话(
找不到这样一种数据结构
) 。那我们就只能按照
间接思路来出发了，硬盘上维护一种数据结构存储我们的数据，内存中选择另外一种数据结构保存数据。当从硬盘读取数据到内存中时，中间做一层转换
。间接思路这种做法是下策，因为中间数据的转换避免不了会引入一些性能的损耗。
那就先按照直观想法出发来找找看，是否存在这样一类数据结构呢？
3.3 直观思路出发
我们先想想，既然我们的目标仍然是
快速、高效读写
，那对应到磁盘上，怎么做到对磁盘快速、高效读写呢？
根据前面的铺垫介绍，大伙应该都知道了那就尽可能的利用磁盘的
顺序 IO
呗。提到顺序 IO ，脑子里第一时间蹦出来的自然就是
追加写
，因为这种方式就是一种典型的顺序写、顺序 IO ，性能挺高的。我们假设用户每个写请求进来，都采用追加写的方式来保存数据。在这种方式下写操作是快了、高效了。
那怎么来读呢？
根据前面的介绍，数据是按照key-value来扁平化存储的。每条记录长度各不相同，既然要保证读，那就得额外保存一些信息来辅助处理用户的读请求。这些额外保存的数据，我们暂且称为
索引
。我们思索一下，在这种追加写的场景下，我们需要保存哪些信息才可以完成正常的读请求呢？其实
每条记录我们只要知道了它写在磁盘的哪个位置(偏移量) offset、占了多长 size 这两个信息。我们就可以对其进行读了
。简而言之，一条记录对应一个这样的二元组索引信息。简单示意图如下所以：

本文插图
到这儿，高效写可以了，维护了索引后，单个记录的读也可以了；但是有个问题我们得想想怎么办？
那就是我们前面提到的排序、范围查找操作
。
在这种场景下，每来一条记录我们都是直接追加的，所以数据在磁盘上本身就是乱序存储的，既然需要