前言

索引是个与数据存储和查询相关的古老话题，目的只有一个：“提高数据获取的性能”。我们知道一本书的前面几页肯定会有一个目录，这个目录式的索引能使我们快速查询想看的内容；把目光转移到计算机上，索引则变得抽象，有时候不好理解。索引保存在哪里，是个什么样的数据结构，计算机领域的索引无外乎也是这两个主题。磁盘上保存有大量的文件，文件系统对这些文件进行管理。文件系统将磁盘抽象为4个部分，依次如下所示。

这当中索引节点表保存了所有文件或目录对应的inode节点（Linux文件系统），通过文件名或目录找到对应的inode节点，通过inode节点定位到文件数据在文件系统中的逻辑块号，最后根据磁盘驱动程序将逻辑块号映射到磁盘上具体的块号。回到数据库方面，数据库保存记录的机制是建立在文件系统上的，索引也是以文件的形式存储在磁盘上，在数据库中用到的最多的索引结构就是B树。尽管索