原文来自于：http://dblab.cs.toronto.edu/courses/443/2013/05.btree-index.html

1. B+树索引概述

在上一篇文章中，我们讨论了关于index的几个中重要的课题：

A) index是保存在磁盘上的一种数据结构，用于提高查询或是扫描record的速度。

B) 排序索引树通过保存page的指针加速record的查找。（ISAM）

C) 维护排序索引树的代价很高，因此，ISAM通过创建overflow page来解决这个问题，但是过多的overflow page会使查询性能从log（指数log）级别降低到线性遍历。

下面我们将介绍一种高度健壮的、比较流行的一种数据结构——B+树，作为ISAM的扩展。

一般说来，B+树是一种高效的基于磁盘保存的数据结构，主要保存(key, value)pair。它支持对key的高效查找，和高效的范围迭代。

B+树提供了这些功能：

A) 快速的record查找

B) 快速的record遍历

C) 不通过overflow page的形式维护排序树结构

B+树背后的关键思想是利用有序平衡树，替代ISAM中的排序树。

2. B+树的定义

B+树是用磁盘上的page作为node节点的树。B+树中的节点可以区分为leaf node（叶子节点）和interior node（内部节点）。

由于每一个node刚好是磁盘中的一个page，在B+树中，我们使用的术语node和page是可以互换的。

2.1 leaf node

leaf node保存数据entry（条目，相当于record），entry的形式是(key, value)。所有的leaf node也被组织成page链表的形式。