本文如理解有误还请随时指出以做更正。
BTREE：
介绍BTREE之前需要引入两个概念一个是B+树，一个是B+树的High-Key的概念,因为BTREE的实现主要依赖B+树。如图1-1所示(借用一下百度的图片)。
B+ 树是一种树数据结构，是一个n叉排序树，每个节点通常有多个孩子，一棵B+树包含根节点、内部节点和叶子节点。
图1-1
High-key: B+树的每一个节点都有一个High-Key值，此值表示此节点或者此节点的子节点的最大值。
1、索引使用场景
BTREE：数据类型范围索引，支持 >
2、BTREE的函数集主要为 索引建立，索引插入，索引扫描，索引删除。因为插入与扫描，删除类似，仅对建立插入做出阐述。
3、为什么BTREE索引选择了B+树
因为B+树压缩了B树的层级，能够有效节省数据库的IO查找操作，极少的降低了性能，但是极大的提高了查询效率。
4、索引的建立
4.1、Btree建立基于基表(需要建立索引的表)的每一个元组完成索引封装(即索引元组)索引元组结构如图1-2所示。
图1-2
4.2、索引元组按照由小到大进行排序，索引元组将来作为B+树的叶子节点，Pi表示ki的上限范围，如图1-3所示。
图1-3
4.3、索引页的结构与普通page页的结构相似，仅是根据B+树的要求每层又区分为最右节点页面、非最右节点页面。
每一层的当前页面填充完成之后，如果并不是最右边的节点，则页面的PageHeader中的linp0元素需要标志此页面的High-Key用于表示此页的数据范围，并把此页的最后一个索引元组itup3复制到其右兄弟节点页面，删除linp3。非最右节点如1-4所示。
图1-4
每一层的当前页面填充完成之后，如果发现是最右边的节点，则页面的PageHeader中的linp0不再需要保持High-key，此时其指向第一个itup1，然后顺移指向其它itup的linp,最后删除linp3，如图1-5所示。
图1-5
4.4、现在索引元组与索引的页面结构都有了，那么现在需要考虑如何建立索引树了。在解释组装索引树之前还需要说明一下页面结构中special space的作用，可以简单的理解为一个页面链表的指针，永远指向右兄弟节点或者用无效表示最右节点。其实索引树的建立采取自下而上的建立方式。为了简化B+树，以二叉树为例。
a)开始组装第一个叶子节点，在第一个页面未灌满之前不停的写入元组，如图1-6。
图1-6
b)第一个叶子节点灌满之后，开始申请并灌入第二个节点，并为第一个节点创建一个父节点并将第一个节点的High-Key写入父节点。让父节 点指向第一个节点，第一个节点的special space指针指向第二个节点(第二个节点为第一个节点的右兄弟节点)。如图1-7。
图1-7
c)当第二个节点灌满之后，则申请第三个新节点，并建立第一层的第一个父节点到第二个节点的指针；为第一层的父节点再建立一个父节点，如图1-8。
图1-8
d)当第三个节点也填充完毕之后，则像开始那样为此节点创建一个指向本节点的父节点，并再次申请一个右兄弟节点，如图1-9。
图1-9
e)如此反复下去则一个完整的索引树建立起来了，但是现在还需要一个索引树的描述页，那就是索引元页，包含了根节点对应的块号，版本信息等。元页这些信息是在创建索引树的过程中收集的。
5、索引的插入
当进行新元组插入时，索引页需要相应的更新。
a)封装新的索引元组，如build所示，不再赘述。
b)根据索引元页确定根节点进行索引树walk-down扫描，扫描过程中内部节点则查找第一个key=scankey，并在扫描过程中记录非叶子节点的节点信息，可以简单理解为路径节点链表，虽然不是很准确,但是便于理解。
为了描述简化，同样以二叉树为例，如图1-10。
图1-10
c)如果叶子节点的空间不够则需要进行叶子节点分裂。
介绍分裂之前需要再引入几个概念：分裂后左节点空闲空间后文简称左节点空闲空间，分裂后右节点空闲空间后文简称右节点空闲空间，空闲差，最佳空闲差。
最佳空闲差 = 当前页面空闲空间 / 16
空闲差又分为非最右节点最佳空闲，最右节点最佳空闲。
分裂原则：分裂位置为左节点空闲空间与右兄弟节点空闲绝对差值 < 最佳空闲差则
取当前索引元组位置为分裂点，否则取下一元组位置为分裂点。
分裂之后创建一个新节点插入父节点中且更新High-Key，如果过程中内部节点需要随着改变也需要做出相应的更新，如图1-11.
图1-11
