纵观
树结构索引的好处：定位记录的I/O减少，索引树的高度一般就是3,4层
树结构中的两种结构
1. ISAM结构
2. B+树结构
ISAM结构（索引顺序存取方法）
- 索引树的结构不变，是静态的
- 多个项插入到一个叶子页，超出了一页，就需要分配另外的页，加入溢出页（这是从溢出区中分配出来的）
搜索的过程：
搜索的数据和索引中的值比较，一层层下去，到达叶子（数据页），然后在主叶子页中搜索，没有的话就去主叶子页对应的溢出页中搜索。
缺点：
- 如果大量的插入操作作用于同一叶子，就会产生很长的溢出页链，这些链非常影响搜索记录的时间。
优点：
- 只有叶子叶被修改对于并发访问也有好处。当一页被访问时，会被申请者锁定，保证它不被该页的其他用户并发修改。
- 索引级的页从不被修改，可以不对索引级页加锁（这是优于B+的一个重要优点）
- 当数据分布和大小相对稳定而使得溢出链很少时，ISAM将优于B+树
B+树（动态索引结构）
- 平衡树
- 叶子页之间用双向链表
- 只有索引级树和叶子级树（即和ISAM相比，没有溢出页）
- 每个节点都要保证最少50%的占有率（假设，每个节点包含m个项的B+树，其中d<=m<=2d，d是B+树的一个参数，秩。根节点是唯一的例外1<=m<=2d）
节点格式
有m个索引项的非叶子页节点包含m+1个指向孩子的指针。叶子页以双向链表的形式连接起来。
（有关搜索，插入和删除的操作，B+都不允许重复）
搜索
在索引树上缩小范围后，通过指针访问叶子页，然后继续通过双向链表进行搜索
插入
注意分裂的问题，因为B+不加入溢出页，当插入的数据多于一个页都可以存放的量的时候，就需要分裂叶子页，这里分裂叶子页过程是这样的
2015-05-07 19:32:02 的屏幕截图.png
2015-05-07 19:32:25 的屏幕截图.png
新插入的8使得新加了一页，因为每一页都会有索引指针指向，这就意味这我们要新增索引项，即复制了5的那项。这一项将会插到父节点中，因为父节点又满了，这就以为这父节点又要分裂。但是这里的分裂和刚刚的分裂优点不一样。新的项（5的那项）‘弹上去’以后，父节点要分裂，这时候的中间的那项17是被‘拉上去’而不是复制的。因为我们这时候不需要副本。
2015-05-07 19:37:16 的屏幕截图.png
这里也有个变种的方法：就是重分布，搜索兄弟节点检查是否还有空位插入。这个想法同样使用于删除中。
删除
删除需要注意到合并的问题。开始时先考虑是否可以重分布，即搜索兄弟节点看是否可以‘过继’过来。如果不行的话，我们就要对两个节点进行合并（注意：合并就代表有页要被删除，这就代表着指针将会减少，父节点可能要被‘拉下来’）
2015-05-07 20:08:07 的屏幕截图.png
2015-05-07 20:07:09 的屏幕截图.png
2015-05-07 20:07:34 的屏幕截图.png
