数据结构索引之杀死攻略（二）
接上一篇《数据结构索引之杀死攻略（一）》：https://blog.****.net/wydyd110/article/details/81904483
目录
3 动态索引
3.1 开场白
一如既往，我先
以搜索引擎为例，在互联网中每时每刻都有大量的页面生成，为了满足用户的不同需求，必须要加入最新的文档返回给用户，比如：在百度上查询“北京天气预报”，如果按照静态索引的话，返回的信息就不是最新的，可能是今天以前的天气预报信息。而动态索引可以很好地解决实时的问题。
在原始的静态索引库搭建好之后，源源不断的会有新的文档加入进来，同时原先的文档索引可能会被删除或者被更改。比如：在视频软件客户端上，视频边下载边播放的功能；当观看一个新的视频时，缓存库会对该视频进行实时缓存，搜索引擎也是一样的，需要及时的将新的文件纳入到缓存库中。
下面介绍一下，用于实现动态索引的数据结构
3.2 B树（B-树）
3.2.1 B树的特征
推荐博文：https://blog.****.net/wydyd110/article/details/81983412
4阶B树（2-4树）
5阶B树（3-5树）
每个节点至多拥有4个关键码，除根节点外每个节点至少拥有2个关键码。
B树还隐含指针
m阶B树的结构定义：
（1）每个结点至多有m个子结点，除根结点与叶结点外，至少有
个子结点
（2）根结点至少有两个子结点（B树只有一个结点时例外）
（3）所有叶结点在同一层
（4）有k个子结点的非根结点恰好包含 k-1 个关键码
（4）含n个关键码的m阶B树，最大高度为logm(n)，最小高度为1/log2(m)
这么多定义，我知道很
然而，下面还有。
B树的性质：
（1）关键码没有重复，左 < 中 < 右
（2）B树把值接近的放在同一个磁盘页中，并采用访问局部性原理
（3）B树保证树中至少有一定比例的结点是满的。提高空间利用率，减少磁盘读取次数。
B树利于一次读入多个关键码，好比要去远方买粉笔，用一节车厢装若干粉笔要比用一节车厢装一支粉笔效率要高。好不容易去一趟远方，能多装点粉笔就多装点啊。
3.2.2 B树的查找
结果要学B树。
呈上一棵（3-5）树，即5阶的B树。
1. 查找75
先对常驻内存的根节点进行一次顺序查找，正确命中75。
2.查找69
先对常驻内存的根节点进行一次顺序查找，这次查找以失败终止于介乎53和75之间的这个引用。对63和69所在的这个节点进行一次顺序查找，成功找到69。
3.查找45
先对常驻内存的根节点进行一次顺序查找，这次查找以失败终止于53左侧的引用。将19和36这个节点通过IO载入内存，并做一次顺序查找，这次查找以失败终止于36右侧的引用，......最终查找失败于41与49之间的引用。
3.2.3 B树的插入
上溢：插入新的关键码后违反了B树的性质，此时需做分裂。
栗子1：
14：a - b - f
55 : （a）- d - k（a已被缓存）
19 ： （a）- c - g（a已被缓存）
栗子2：
4阶B树，每个节点的分支至多4，至少2；等价的每个节点所包含的关键码数至多3，至少1
3.2.4 B树的删除
下溢：删除关键码后违反了B树的性质，此时需做旋转或合并。
栗子：
3.3 B+树
推荐博文：https://blog.****.net/wydyd110/article/details/81983412
3.3.1 B+树的特征
B+树是B树的一种变形，有着比B树更高的查询性能
（1）所有的关键码均出现在叶结点上，各层结点中的关键码均是下一层相应结点中最大关键码（或最小关键码）的复写
（2）B树中，无论中间结点还是叶子结点都带有数据。
（来源于：伯乐专栏作者/玻璃猫）
B+树中，只有叶子结点带有数据，其余中间结点仅仅是索引。因此，同样大小的磁盘页可以容纳更多的结点。数据量相等的情况下，B+树的结构比B-树更加“矮胖”，查询时I/O次数也更少。
（来源于：伯乐专栏作者/玻璃猫）
（3）有k个子结点的结点必定有k个关键码
3.3.2 B+树的查找
（1）单元素查询
B+树的单元素查找流程与B树差不多，不同的是
（来源于：伯乐专栏作者/玻璃猫）
（2）范围查询，查询3-11间的元素
（来源于：伯乐专栏作者/玻璃猫）
（来源：伯乐专栏作者/玻璃猫）
B+树的范围查询要简单得多，只需在链表做遍历即可。
3.3.3 B+树的插入
B+树的插入——分裂与B-树大同小异，但要保证上一层结点中有这两个结点的最大关键码（或最小关键码）。
（栗子后续补充）
3.3.4 B+树的删除
当关键码下溢出时，与左或右兄弟进行调整，或者合并
关键码在叶结点层删除后，其在上层的复本可以保留，也可以替换为新的最大关键码（或最小关键码）（栗子后续补充）
3.4 B树与B+树的应用
终于到总结了
3.4.1 为什么使用B-Tree/B+Tree
文件系统及数据库系统普遍采用B-/+Tree作为索引结构。
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
3.4.2 B-Tree/B+Tree对比
B树
B+树
（1）B+ 树的存储效率更高、检索层次更少（树较矮）
（2）所有查询都要查找到叶子节点，查询性能稳定
（3）所有叶子节点形成有序链表，便于范围查询
（4）B+ 树应用得更为广泛
- 数据库系统主码（primary key）索引
- 基于B+树的磁盘文件虚拟存储存取管理 VSAM (Virtual Storage Access Method)，取代了基于多分树的 ISAM
- MySQL索引采用B+树作为数据结构
《数据结构索引之杀死攻略》还未完结，下面跳转到下一篇《数据结构索引之杀死攻略（三）》：
https://blog.****.net/wydyd110/article/details/82012960