多级索引
由于全量索引数据量较大，不能直接全部放入内存中，需要分级，将上层稀疏索引放入内存中，降低IO次数。
辅助索引必须密集的，每个搜索关键字值都有一个索引条目，辅助索引必须包含指向所有记录的指针；如果辅助索引只存储部分搜索关键字值，则具有中间搜索关键字值的记录可能位于文件中的任何位置，通常，如果不搜索整个文件，我们就无法找到它们。
B+树
B+树都是平衡的。也就是说，从根到叶节点的每条路径的长度都是相同的。此属性是B+树的要求。B+树中的“B”代表““balanced(平衡)”
B+树索引结构是几种索引结构中使用最广泛的，尽管需要插入和删除数据（影响性能），但仍能保持其效率。B+树索引采用平衡树的形式，其中从树根到树叶的每条路径都具有相同的长度。树中的每个非叶节点（除了根）都有在n/2和n个子节点之间，其中n对于特定的树是固定的；根有2到n个孩子。树的高度路径不大于log n/2（N）,n的值通常在50或100左右。 N为总记录，n为子节点大小。 根节点信息通常在内存缓存区中。
B+树的一个典型节点。它包含最多n−1个搜索关键字值K1、K2、…、Kn−1和n个指针P1、P2、…、Pn。节点内的搜索关键字值按排序顺序保存；因此，如果i＜j，那么Ki＜Kj.
| P1 | K1 | P2 | K2 | ... | Pn-1 | Kn-1 | Pn |
|---|
允许叶节点包含的值少至（n−1）∕2个（向上取整）。在我们的例子B+树中，当n=4时，每个叶子必须至少包含2个值，最多包含3个值。
一个非叶节点最多可以容纳n个指针，并且必须至少容纳n/2 （向上取整）个指针。节点中指针的数量称为节点的fanout(扇出、输出)。非叶节点也称为内部节点。
非唯一索引实现
大多数数据库实现使搜索关键字唯一，如下所示：假设关系r的所需搜索关键字属性ai是非唯一的。设Ap是r的主键，然后是唯一的复合搜索键（ai，Ap）而不是ai。（任何一组与ai一起保证唯一性的属性也可以用来代替Ap。）.
B+树结构和内存中的树结构（如二叉树）之间的一个重要区别是节点的大小，因此也是树的高度。在二叉树中，每个节点都很小，最多有两个指针。在B+树中，每个节点都很大，通常是一个磁盘块，一个节点可以有大量指针。因此，B+树往往又胖又矮，不像瘦高的二叉树。
B+树 插入
当所在叶子节点满了（有n-1个值，再插入一个新值）后，通常，我们采用n个搜索关键字值（叶中的n−1值节点加上插入的值），并将第一个（n/2）放在现有节点中，将其余值放在新创建的节点中。在拆分了一个叶节点之后，我们必须将新的叶节点插入B+树结构中。在我们的示例中，新节点将“Califieri”作为其最小的搜索关键字值。我们需要将一个具有此搜索键值的条目和一个指向新节点的指针插入到被拆分的叶节点的父节点中。如果父节点中有空间容纳新条目，可以在不进一步拆分节点的情况下执行此插入。如果没有空间，则必须拆分父对象，需要将条目添加到其父对象中。在最坏的情况下，沿着根路径的所有节点都必须被拆分。如果根本身被拆分，整个树就会变得更深。非叶子节点满了，处理逻辑为(n+1)/2, (n+1)/2+1两个指针，中间值上升到父节点。
尽管B+树只能保证节点至少有一半满，但如果按随机顺序插入条目，节点的平均满数可能会超过三分之二。另一方面，如果按排序顺序插入条目，则节点将仅为半满。
叶子节点拆分重定位影响
由于叶节点拆分而重新定位记录，因此不需要对任何此类辅助索引(保存主键值，而不是指针)进行任何更新。然而，使用辅助索引查找记录现在需要两个步骤：首先，我们使用辅助索引来查找主索引搜索关键字值，然后使用主索引来查找相应的记录。
因此，这种方法大大降低了由于文件重组而导致的索引更新成本，尽管它增加了使用辅助索引访问数据的成本。
执行索引批量加载的一种有效方法如下：
首先，创建一个包含关系索引项的临时文件，然后根据正在构建的索引的搜索键对文件进行排序，最后扫描排序后的文件并将项插入索引。有一些高效的算法可以对大型关系进行排序，稍后将在第15.4节中描述，假设有合理数量的主内存可用，这种算法甚至可以对大型文件进行排序，其I/O成本与读取文件几次的I/O成本相当。
覆盖索引是存储某些属性（搜索关键字属性除外）的值以及指向记录的指针的索引。存储额外的属性值对辅助索引很有用，因为它们允许我们只使用索引来回答一些查询，甚至不需要查找实际记录。
对于需要支持每秒大量随机写入/插入的应用程序来说，基本的B+树结构并不理想。已经提出了几种替代索引结构来处理具有高写入/插入速率的工作负载，包括日志结构的合并树和缓冲区树。
LSM树（log-structured merge tree）
LSM树由几个B+树组成，从一个称为L0的内存中树开始，到磁盘上的树L1、L2、…、Lk，当记录第一次插入LSM树时，它被插入到内存中的B+树结构L0中。为这个树分配了相当大的内存空间。该树随着处理更多的插入而增长，直到它填满了分配给它的内存。此时，我们需要将数据从内存中的结构移动到磁盘上的B+树中。如果树L1为空，则将整个内存中的树L0写入磁盘以创建初始树L1。然而，如果L1不为空，则L0的叶级以递增关键字顺序扫描，并且条目与L1的叶级条目合并（也以递增关键字次序扫描）。合并后的条目用于创建一个新的B+树，使用自下而上的构建过程。注意，旧L1树的叶级中的所有条目，包括没有任何更新的叶节点中的条目，都被复制到新树，而不是对现有L1树节点执行更新。这带来了以下好处。
1.新树的叶子是按顺序定位的，避免了后续合并过程中的随机I/O。
2.叶是满的，避免了页面拆分时可能出现的部分占用的叶的开销。
每个级别（L0除外）最多可以有b个树，而不是只有1个树。LSM树的这种变体被称为阶梯合并索引（stepped-merge index）。与每个级别只有一棵树相比，steppedmerge索引显著降低了插入成本，但由于可能需要搜索多棵树，它可能会导致查询成本增加。第24.1节中描述的称为Bloom过滤器的基于位图的结构用于通过有效地检测特定树中不存在搜索关键字来减少查找次数。Bloom过滤器占用的空间非常小，但它们在降低查询成本方面非常有效。
删除操作导致插入新的删除条目，该条目指示要删除哪个索引条目。插入删除条目的过程与插入正常索引条目的过程相同。然而，查找必须执行额外的步骤。如前所述，查找从所有树中检索条目，并按键值的排序顺序合并它们。如果某个条目有一个删除条目，那么这两个条目将具有相同的键值。因此，查找将找到要删除的密钥的删除条目和原始条目。如果找到删除条目，将筛选出要删除的条目，并且不会将其作为查找结果的一部分返回。
LSM树最初是为了减少磁盘的写和寻道开销而设计的。基于闪存的SSD对于随机I/O操作具有相对较低的开销，因为它们不需要寻道，因此避免LSM树变体提供的随机I/O的好处对于SSD来说并不特别重要。然而，请记住，闪存不允许就地更新，即使向页面写入单个字节也需要将整个页面重写到新的物理位置；页面的原始位置最终需要被擦除，这是一个相对昂贵的操作。与传统的B+树相比，使用LSM树变体的写入次数减少，当LSM树与SSD一起使用时，可以提供显著的性能优势。