关系数据库中的索引一般使用B+树结构（或其变体）
有几点值得一说：
1. B是”Balanced”的意思，意即从树根到所有树叶的路径都一样长
2. 图中每个结点都是一个磁盘block
3. 叶结点中向下的箭头指向数据记录
4. 增删记录时可能会导致结点的递归分裂或合并
5. 每个叶节点的最右边有一个指针指向下一个更大的索引项所在的叶结点
性能：
1. 增、删、查（单条记录）的I/O次数约等于树的层高
2. 树的层数取决于记录数和每个block可以存放的索引项的数目（这个数目也决定了一个结点可以有多少个子结点）。如果block大小=4k, 索引字段类型是整型，那么一个3层的B-树可以索引1500多万的记录数(具体算法参见hector garcia-molina《数据库系统实现)。 也就是说，大部分情况下，三层就够了。
3. 每个叶节点的最右边的指针可以使Range Query成为可能(即范围查询, key between 100 and 200 这种)。