前言
磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上(即寻道上)。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间Ts。
一般查找我们都可以使用树型结构
B树
B 树又叫平衡多路查找树。一棵m阶的B 树的特性如下
- 树中每个结点最多含有m-1个孩子（m>=2）；
- 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
- 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
- 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息
小结:
假如是m阶,则关键字最多有m-1个(这在页的分裂比较重要,后面会详细说),然后B树的数据是每个节点都会有的(这导致每个页可以存储的关键字数目变少,变相的导致树会变高,而树越高,磁盘寻道次数就可能越多,就越可能浪费时间)
B+树
B+树为了控制树的高度,只在叶子节点存储数据（这样非叶子节点每一页可以存储更多的关键字,进而很可能不用下沉到叶子节点就能找到我们想要的信息,也大概率减少了寻道次数）,当然非叶子节点里面的数据是冗余的,即非叶子节点关键字是由叶子节点里面的关键字中的最小的数组成的,可以详见下面的数据结构.
备注:B+树,是假如为m阶,则每个节点最多会有m个关键字
如图所示,是一棵4阶B+树,每个节点最多四个关键字,叶子节点从左往右,从小到大,通过指针连接是一个双向链表.(即排好序的,我们就可以用二分查找法,速度会很快)
我们再来看B+树的分裂过程
会引发B+树的分裂操作包括插入和删除,引发条件及关键字数超过要求或者为了空间利用率
B+树的插入操作
即分裂完后,不断的将中间节点往上提
B+树的删除操作
B+树使用填充因子（fill factor）来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样必须保证删除后叶节点中的记录依然排序，同插入一样，B+树的删除操作同样需要考虑如表5-2所示的三种情况，与插入不同的是，删除根据填充因子的变化来衡量。
即不断的合并,然后更新Index Page
Mysql里面的分裂
上面我们讲的分裂都是从中间节点开始,但实际上这样会导致页空间的浪费.
比如说记录如下
1,2,3,4,5,6,7,8,9
插入式根据自增顺序进行的,若这时插入10，则会分裂为两页
P1:1,2,3,4
P2:5,6,7,8,9,10
又由于插入是顺序的,那么P1这个页将不会再有记录插入,从而导致空间浪费
那么InnoDB引擎的具体优化措施
假如现在有一页数量为5,现在插入一个数,假如该数后面还有3个数(即超过了一半),则将分裂点为插入数后3位的位置
否则分裂点就为插入数定位到的位置
前面我们分析了,当有大量分裂时,会导致大量的随机寻道,从而降低性能,所以就可以使用LSM树
LSM树是什么呢?
它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中，而可以先将最新的数据驻留在内存中，等到积累到最后多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起)。
LSM具有批量特性，存储延迟。当写读比例很大的时候（写比读多），LSM树相比于B树有更好的性能。因为随着insert操作，为了维护B树结构，节点分裂。读磁盘的随机读写概率会变大，性能会逐渐减弱。 多次单页随机写，变成一次多页随机写,复用了磁盘寻道时间，极大提升效率。
LSM Tree弄了很多个小的有序结构，比如每m个数据，在内存里排序一次，下面100个数据，再排序一次……这样依次做下去，我就可以获得N/m个有序的小的有序结构。
在查询的时候，因为不知道这个数据到底是在哪里，所以就从最新的一个小的有序结构里做二分查找，找得到就返回，找不到就继续找下一个小有序结构，一直到找到为止。
很容易可以看出，这样的模式，读取的时间复杂度是(N/m)*log2N 。读取效率是会下降的。
当然也可以做一些优化
a、Bloom filter: 就是个带随即概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。
b、compact:小树合并为大树:因为小树他性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了
