3.2 索引结构-B树和B+树
B树在先修课程《数据结构》中做过讲解，这里不再赘述。索引结构中我们重点介绍B+树。
B+树概述
这里提供 m 阶B+树的一种实现方式：
-
非叶结点的关键字个数与孩子结点个数相等。其存储的关键字有序排列，且与存储的孩子结点指针一一对应，每个关键字都是对应子树的最大关键字。
-
除根结点以外，每个内部结点的孩子数都在 [(m+1)/2, m] 范围内。
-
最下层结点（叶结点）存储了全部的原始数据（“键-值”对），每个叶结点存储的数据按照"键"有序排列。叶结点可以按照键值从小到大连成单向或双向的链表。
在数据库索引中，每页作为一个结点（这样一个B+树结点所占的最大空间为页面大小），是否叶结点、叶结点链表指针等信息可以存储在页头中。非叶结点要存储若干个 (关键字, 孩子页号) 结构，叶结点要存储若干个 (关键字, 记录位置) 的“键-值”对结构，这些结构可以像表内一条记录一样存储。
如果要在多个列上创建索引，可以将这些列的值拼接成多元组，对其建立一种偏序关系（如：对于任意两个多元组，先比较第一列的值，相等的话比较第二列的值，依此类推确定它们的大小关系），并将多元组作为B+树的关键字。多维索引（如：R树）针对关键字为多维数据的情况进行了特殊的优化。不过多维索引超出了本课程范围，大家感兴趣的话可以自行查找资料进行实现。
查找
给定查找键，对于非叶结点，找到不小于查找键的第一项（如果不存在则选择结点存储的最大项），选择对应的孩子页为下一个查找结点。从根结点开始对每个途经结点重复上述过程，直到到达某个叶结点。找到该叶结点中不小于查找键的第一项（可能不存在），对应的记录的相应属性值为表中不小于查找键的最小值。如果要查找某个关键字范围 [a, b] 内的记录，可以先找到关键字 a 对应的“键-值”对，然后沿叶结点链表顺序查找，直到某个关键字大于b。
插入
给定待插入记录，将其对应属性值作为查找键，可以找到B+树中的一个“键-值”对，其具有不小于查找键的最小关键字。将该记录的相应关键字和记录位置作为新的“键-值”对插入到查找到的位置（可能需要移动B+树中现有的数据）。如果叶结点最大关键字改变，可能需要逐级更新父结点的相应关键字。如果某结点发生上溢，则将其分裂为两个分支数相近的结点，都作为该结点父结点的子结点，父结点也要处理可能的上溢；如果该结点为根结点，则需要创建新的根结点作为父结点。
删除
给定查找键，可以找到B+树中的一个“键-值”对，然后沿叶结点链表顺序扫描，将关键字等于查找键的“键-值”对都删掉。如果叶结点最大关键字改变，可能需要逐级更新父结点的关键字。如果某结点发生下溢，且其为根结点，其子结点在某些情况下可能成为新的根结点；如果其左/右兄弟有多余的孩子结点，可以过继给它；否则可以将其与左/右兄弟合并成一个结点，删除或更新父结点的关键字，父结点也要处理可能的下溢。