B树
1、概念
- 每个节点最多有m-1个关键字，m表示阶数（二叉树m=2）
- 根节点最少可以只有一个关键字
- 非根节点至少有Math.ceil(m/2)-1个关键字，一半左1个最少
- 每个节点中的关键字都按照从小到大顺序排列，每个关键字的左子树所有关键字都小于它，而右子树中的所有关键字都大于它
- 所有叶子节点都位于同一层，或者说根节点到每个叶子结点的长度都相同
B树
1.1、翻译一遍： - 根节点不能为空，为空没法查找了
- 每个节点最多有m-1个关键字，因为关键字有左右空隙可以长出树枝，m-1个关键字刚好能长出m个树枝
- 非根节点至少有一半左1个关键字，再少的话增加深度，浪费空间，再多的话调整旋转的时候就比较麻烦，相当于一个权衡
- 同一节点关键字按序存储，左空隙的枝子都小，右空隙的枝子都大
- 所有叶子节点位于同一层，保证查找稳定
1.2、B树中数据的解释 - 每个节点存储了关键字key和关键字对应的数据data以及孩子节点的指针
- 把一个key和其对应的data称为一个记录
- 数据库应用中key表示键，data表示这个键对应的条目在硬盘上的逻辑地址
- 一般应用中B树的阶数m大于100
2、增删改查
2.1、插入
以5阶B树为例
a）在空树中插入39，此时根节点就1个key，根节点也是叶子结点
clip_image002[4]
b）继续插入22，97和41，根节点有4个key
clip_image004
c）继续插入53，插入后大于5-1，此时以中间key 41为中心开始分裂仪式，分裂后小于它的在左孩子，大于它的在右孩子。
clip_image006
d）依次插入13，21，40，同样会造成分裂，结果如下图所示。
clip_image010
e）依次插入30，27, 33 ；36，35，34 ；24，29，结果如下图所示。
clip_image012
f）插入key值为26的记录，插入后的结果如下图所示。
clip_image014
当前结点需要以27为中心分裂，并向父结点进位27，然后当前结点指向父结点，结果如下图所示。
clip_image016
进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示。
clip_image018
分裂后当前结点指向新的根，此时无需调整。
g）最后再依次插入key为17,28,29,31,32的记录，结果如下图所示。
clip_image020
缺点
一般来说，对于确定的m和确定类型的记录，结点大小是固定的，无论它实际存储了多少个记录。但是分配固定结点大小的方法会存在浪费的情况，比如key为28,29所在的结点，还有2个key的位置没有使用，但是已经不可能继续在插入任何值了，因为这个结点的前序key是27,后继key是30,所有整数值都用完了。所以如果记录先按key的大小排好序，再插入到B树中，结点的使用率就会很低，最差情况下使用率仅为50%。
2.2、删除
a）原始状态
clip_image021
b）在上面的B树中删除21，删除后结点中的关键字个数仍然大于等2，所以删除结束。
clip_image023
c）在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28（原27）的右孩子结点中删除28。删除后的结果如下图所示。
clip_image025
删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。结果如下图所示。
clip_image027
d）在上述情况下接着32，结果如下图。
clip_image029
当删除后，当前结点中只key，而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。
clip_image031
当前结点key的个数满足条件，故删除结束。
e）上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。
clip_image033
同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。
clip_image035
同理，对于当前结点而言只能继续合并了，最后结果如下所示。
clip_image037
合并后结点当前结点满足条件，删除结束。
删除的关键
没有钱从兄弟借，兄弟没有再找父母拿，父母还没有那么大家搭伙过日子（即父母兄弟和自己一起过）
B+树
image.png
2.1、概念
- 与B树性质基本相同，不同的是以下两条
- 所有数据都保存在叶子节点中，枝节点只保存索引
- 每个叶子节点都存有相邻叶子节点的指针，叶子节点按照关键字大小自小而大排序连接
2.2、插入操作
a）空树中插入5
clip_image041
b）依次插入8，10，15
clip_image043
c）插入16
clip_image045
插入16后超过了关键字的个数限制，所以要进行分裂。在叶子结点分裂时，分裂出来的左结点2个记录，右边3个记录，中间key成为索引结点中的key，分裂后当前结点指向了父结点（根结点）。结果如下图所示。
clip_image047
当然我们还有另一种分裂方式，给左结点3个记录，右结点2个记录，此时索引结点中的key就变为15。
d）插入17
clip_image049
e）插入18，插入后如下图所示
clip_image051
当前结点的关键字个数大于5，进行分裂。分裂成两个结点，左结点2个记录，右结点3个记录，关键字16进位到父结点（索引类型）中，将当前结点的指针指向父结点。
clip_image053
当前结点的关键字个数满足条件，插入结束。
f）插入若干数据后
clip_image055
g）在上图中插入7，结果如下图所示
clip_image057
当前结点的关键字个数超过4，需要分裂。左结点2个记录，右结点3个记录。分裂后关键字7进入到父结点中，将当前结点的指针指向父结点，结果如下图所示。
clip_image059
当前结点的关键字个数超过4，需要继续分裂。左结点2个关键字，右结点2个关键字，关键字16进入到父结点中，将当前结点指向父结点，结果如下图所示。
clip_image061
当前结点的关键字个数满足条件，插入结束。
B+树插入关键
分裂之后子节点仍然保存着这个key，因为叶子节点要保存key value
2.2、删除操作
a）初始状态
clip_image063
b）删除22,删除后结果如下图
clip_image065
删除后叶子结点中key的个数大于等于2，删除结束
c）删除15，删除后的结果如下图所示
clip_image067
删除后当前结点只有一个key,不满足条件，而兄弟结点有三个key，可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9，删除结束。
clip_image069
d）删除7，删除后的结果如下图所示
clip_image071
当前结点关键字个数小于2，（左）兄弟结点中的也没有富余的关键字（当前结点还有个右兄弟，不过选择任意一个进行分析就可以了，这里我们选择了左边的），所以当前结点和兄弟结点合并，并删除父结点中的key，当前结点指向父结点。
clip_image073
此时当前结点的关键字个数小于2，兄弟结点的关键字也没有富余，所以父结点中的关键字下移，和两个孩子结点合并，结果如下图所示。
clip_image075
删除关键
- 符合条件直接删除
- 兄弟都没钱了，直接和兄弟链表合并（横向，不需要通过父母）
- 兄弟都没钱了，而且兄弟合并的时候不符合子树个数规定了，那么父母下移，父母兄弟自己搭伙过日子
3、磁盘与B树
3.1磁盘的构造
磁盘是一个扁平的圆盘(与电唱机的唱片类似)。盘面上有许多称为磁道的圆圈，数据就记录在这些磁道上。磁盘可以是单片的，也可以是由若干盘片组成的盘组，每一盘片上有两个面。如下图11.3中所示的6片盘组为例，除去最顶端和最底端的外侧面不存储数据之外，一共有10个面可以用来保存信息。
image.png
当磁盘驱动器执行读/写功能时。盘片装在一个主轴上，并绕主轴高速旋转，当磁道在读/写头(又叫磁头) 下通过时，就可以进行数据的读 / 写了。
一般磁盘分为固定头盘(磁头固定)和活动头盘。固定头盘的每一个磁道上都有独立的磁头，它是固定不动的，专门负责这一磁道上数据的读/写。
活动头盘 (如上图)的磁头是可移动的。每一个盘面上只有一个磁头(磁头是双向的，因此正反盘面都能读写)。它可以从该面的一个磁道移动到另一个磁道。所有磁头都装在同一个动臂上，因此不同盘面上的所有磁头都是同时移动的(行动整齐划一)。当盘片绕主轴旋转的时候，磁头与旋转的盘片形成一个圆柱体。各个盘面上半径相同的磁道组成了一个圆柱面，我们称为柱面 。因此，柱面的个数也就是盘面上的磁道数。
3.2磁盘的读/写原理和效率
磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、块号(磁道上的盘块)。
读/写磁盘上某一指定数据需要下面3个步骤：
(1) 首先移动臂根据柱面号使磁头移动到所需要的柱面上，这一过程被称为定位或查找 。
(2) 如上图11.3中所示的6盘组示意图中，所有磁头都定位到了10个盘面的10条磁道上(磁头都是双向的)。这时根据盘面号来确定指定盘面上的磁道。
(3) 盘面确定以后，盘片开始旋转，将指定块号的磁道段移动至磁头下。
经过上面三个步骤，指定数据的存储位置就被找到。这时就可以开始读/写操作了。
访问某一具体信息，由3部分时间组成：
● 查找时间(seek time) Ts: 完成上述步骤(1)所需要的时间。这部分时间代价最高，最大可达到0.1s左右。
● 等待时间(latency time) Tl: 完成上述步骤(3)所需要的时间。由于盘片绕主轴旋转速度很快，一般为7200转/分(电脑硬盘的性能指标之一, 家用的普通硬盘的转速一般有5400rpm(笔记本)、7200rpm几种)。因此一般旋转一圈大约0.0083s。
● 传输时间(transmission time) Tt: 数据通过系统总线传送到内存的时间，一般传输一个字节(byte)大概0.02us=2*10^(-8)s
磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间Ts
4、B树与数据库、磁盘
主存和磁盘之间的数据交换不是以字节为单位的，而是以n个扇区为单位的（一个扇区有512字节），通常是4KB（8个扇区），8KB（16个扇区），16KB，……64KB为单位的。假设，我们现在选择4KB作为内存和磁盘之间的传输单位，那么我们在设计B+树的时候，不论是索引结点还是叶子结点都使用4KB作为结点的大小。我们这时不妨再假设一个记录的大小是1KB，那么一个叶子结点可以存4个记录。而对于索引结点（大小也是4KB），由于只需要存key值和相应的指针，所以一个索引结点可能可以存储100~150个分支，我们不妨就取100吧。当然这和B树和B+树的插入、删除图文详解第2节和第3节中的情况不太一样，因为现在索引结点的阶数是100，而叶子结点的阶数是4，两者并不一致，但这并没有什么问题。
clip_image002
我们考虑如上图所示的B+树，下面的B+树有三层，两层是索引结点，最后一层是叶子结点。那么这个三层的B+树最多可以存400万个记录。如果这个B+树存储到硬盘中，我们怎么根据记录的key找到对应的记录呢？首先我们要读取这个B+树的根结点到内存（花费一个IO的时间）然后在内存中进行索引，根据key找到对应的分支，再将这个分支所指向的第二层索引结点读取到内存中（花费第二个IO时间）然后在内存中进行索引，同样根据key找到对应的分支，而这个分支指向的就是叶子结点，我们最后将这个叶子结点读取到内存中（花费的第三个IO时间）判断是否存在这个记录。这样我们只需要通过三次IO时间就从400万个记录中找到了对应的key记录，可以说是非常快了。快速的原因是，索引结点中不存数据，只存键和指针，所以一个索引结点就可以存储大量的分支，而一个索引结点只需要一次IO即可读取到内存中。
网友评论