原文地址
附视频讲解：https://www.youtube.com/watch?v=aZjYr87r1b8
b站搬运
导读
1. 数据读取时主要时间开销
从概念模型上来讲，从磁盘读出一条数据需要两步：
- 将磁头移动到数据所在的扇区，即找到数据所在的页，将这一页数据加载到内存
- 在内存中，找到数据所在的偏移量，并返回该记录
这两步中，第1步消耗的时间远远大于第2步，其原因是需要移动磁头到给定扇区，时间开销由寻道和延迟两部分构成，通常在毫秒级。而从内存直接读取数据，时间为纳秒级。
2.优化的方式
由于主要的时间开销来源于寻找数据所在的页。因此优化寻找数据所在页的需求是非常紧急且重要的。
对于给定大小的数据量（比如2^ 20条）、平均每条记录所占用的内存空间（比如2^ 7byte）和每一页的大小（如4kb），那么平均每页的记录数和所需的数据页数就可以确定，分别是(32条和2^15页)。如果使用遍历的方式，将每一页加载到内存然后搜索，那么最坏情况下需要1万次的读取数据页的操作才能搜索到给定记录。这就好像我有一本书，我要从第一页一指翻到最后一页，才能找到我要读到的某一行文字，这显然不太高效。
优化的办法是建立索引，将数据按索引排序，对于每一条数据，我可以建立一个索引+指针来指向该数据的起始地址。那么我就可以将这个索引存起来，并使用指针指向该记录。现在需要 2^ 20个索引，假设每条索引和指针共占8byte空间，那么所需的索引页为2^ 11（2^ 20 * 8 / 4kb）页。此时如果遍历索引页，然后再去找到对应的记录，最坏需要2^11 + 1次读取。显然效率高了些。
如果利用递归的思想，对索引页再建索引（是不是在内存管理中有类似的想法，对页表建立页表）。比如，对这2^20条数据的索引建立索引。对于给定的一页，它的第一条索引是确定的。那么将第一条索引再存到另一个索引中(索引的索引)，假设索引都连续，那么对于给定的一个索引，就可以根据索引的索引找到这个索引所在的页。然后找到这个索引，根据这个索引指向的数据去读取数据。比如：检索索引15，它在0到31之间，便可以知道它在第一个数据页上，通过之前保存起来的指针即可访问到该页。此时，由于更上层的索引更稀疏了，因此可以保存更多的索引，使每一页能表示更多的数据。递归到最终只需1页就能保存某一级索引的时候，就可以停止递归了。此时根据索引来访问数据，只需要查每一级索引中的某一页，就可以确定下一级索引所在的页。直到最底一层的索引，它指向了数据。
那么需要读取的总页数为索引级数+1。这个次数远远小于总数据页数。
使用索引的好处在于：第一，将数据进行了分桶，对于落在桶内区间段的索引，都可以通过一个指针访问到对应的数据页。 第二，索引所占的内存要远远小于1条记录所占的空间，因此个索引页能保存非常多的索引。
以上面的例子而言，索引如图所示
