B树出现的动机
1 内存越来越小： 即使内存的绝对容量在增加，但相对容量在减少；B树多用在内存里放不下，大部分数据存储在外存上时。因为B树层数少，因此可以确保每次操作，读取磁盘的次数尽可能的少。
2 存储容量的增长速度远远小于应用问题规模的速度；典型的数据集都已Tb为单位
3 高速缓存
4 磁盘和内存在访问速度 ms/ns = 10^6 天上方数日，人间已千年 CPU RAM Disk Array从高级别到低级别，访问速度依次降低
5 内存访问需要1s，而外存需要一天
6 从内存到外存的读取数据：采取页面缓冲的方式，就像尽量一次大批量的采购粉笔
B树的结构与特点
1 平衡的多路搜索树：若干个二路节点经过合并组成 n个关键码 n+1路分支，相比平衡二叉树，更宽更矮
2 m阶B树：也就是M路B树，树高H = 外部节点的深度
3 所有的叶节点的深度统一；外部节点的深度统一相等(数值为空de叶节点)
4 m阶次的含义:每个超级节点规模的上限和下限（2，4）树红黑树，（3，6）树
5 m阶每个节点的分支树之多是m 至少树根是大于等于2；其他节点是大于等于m/2取上整，等价的，每个节点所包含的关键字的码数至多是m-1 至少是1
6 也称为：（[m/2]，m）树 []是取上整
B树的表示和实现
1 紧凑表示：外部节点和引用：将节点简化成一个点
2 B树的定义与实现：实现B树的节点类，每一个节点包含n个关键码和n+1个分支
parent key 关键码 child
3 构造空节点；构造初始规模为1的节点
B树的查找：
1 因为B树存储的东西太多，根本不能由内存容纳，需要放在外存
2 只需要将必须的节点放入内存中，尽量减少比如I/O的操作次数，比如活跃类的节点：根节点常驻内存
3 内存中的顺序查找和I/O操作相间隔组成的查找序列；查找每深入一层，就会引入一次I/O操作将下层节点读入内存；如果还是失败，根据失败方向的引用：找到下一层节点
4 最坏的情况到达B树底层的叶节点
5 针对45和49的查找是一致的，以41到49的外部节点的引用失败而告知，失败的话必然是存在与外部节点。如果在第r个关键码失败，也将深入到第r+1个后代引用
6 B树查找的运行时间：O(logn)，最主要的因素。树的高度，在每一个高度时间：I/O操作是主要占用时间；有序向量的顺序查找（二分查找时，比顺序查找更低），要尽量设计成与读I/O操作时间相接近，这样的话实验证明，操作效率更高;每个节点内所含关键码的数值，大致取为几百。
7 B树树高的范围进行界定，树根第0层，叶子节点：第h-1层
8 N个内部节点，N+1个外部节点
N种成功的可能，N+1种失败的可能
B树的插入——上溢——分裂
插入：
4阶B树的特点是
每个节点的分支树之多是4 至少是2等价于每个节点所包含的关键字的码数至多是3 至少是1，当不满足条件时，就会发生上溢
1 B树增高的唯一原因：为了解决上溢的现象，就需要在上溢的节点中选取中位数（向上取整的那种），将该中位数放在父节点中，上溢的现象是单调减的!
2 当插入元素使得上溢层层到达根的时候，也就是说，根节点也达到了上溢，此时选取中位数，一分为二，以中位数为新的根节点，B树的高度增加1，也是跟节点的修正案的作用（修正案：根节点的）
3 上溢修改的时间复杂度为小于等于O(1)xh = O(h)
B树的删除——下溢——合并
1 当B树的删除，使得剩下的树结构不满足B树的特点时，就成为发生了下溢现象
2 出现此现象，需要对树进行旋转，和修改；具体来说 在删除节点之后 需要进行合并操作；而且这种合并操作会不断的向上蔓延 直到树根；而树根节点只含有唯一的一个关键码；以致于在借出这个关键码之后 树根成为空节点
3 这也是B树高度得以下降的唯一可能
4 下溢修改的时间复杂度为小于等于O(1)xh =O(h)