本节目标1. 常见的搜索结构2. B-树概念3. B-树的插入分析4. B-树的插入实现5. B树和B*树6. B-树的应用目录1. 常见的搜索结构2. B树概念3. B-树的插入分析4. B-树的插入实现5. B树和B*树6. B-树的应用1. 常见的搜索结构种类数据格式时间复杂度顺序查找无要求O ( N ) O(N)O(N)二分查找有序O ( log ⁡ 2 N ) O(\log_2 N)O(log2​N)二叉搜索树无要求O ( N ) O(N)O(N)二叉平衡树AVL树和红黑树无要求O ( log ⁡ 2 N ) O(\log_2 N)O(log2​N)哈希无要求O ( 1 ) O(1)O(1)以上结构适合用于数据量相对不是很大、能够一次性存放在内存中并进行数据查找的场景。如果数据量很大比如有 100G 数据无法一次放进内存中那就只能放在磁盘上了。如果放在磁盘上又需要搜索某些数据那么如何处理呢可以考虑将存放关键字及其映射数据的地址放到一个内存中的搜索树的节点中访问数据时先取这个地址再去磁盘访问数据。使用平衡二叉搜索树的缺陷平衡二叉搜索树的高度是log ⁡ N \log NlogN这个查找次数在内存中是很快的。但是当数据都在磁盘中时访问磁盘速度很慢在数据量很大时log ⁡ N \log NlogN次磁盘访问是一个难以接受的结果。使用哈希表的缺陷哈希表的效率很高是O ( 1 ) O(1)O(1)但是一些极端场景下某个位置冲突很多导致访问次数剧增也是难以接受的。那如何加速对数据的访问呢提高 IO 的速度SSD 相比传统机械硬盘快了不少但是还是没有得到本质性的提升降低树的高度–多叉平衡树2. B树概念1970 年R. Bayer 和 E. McCreight 提出了一种适合外查找的树它是一种平衡的多叉树称为 B 树后面有一个 B 的改进版本 B 树有些地方把 B 树写成 B-树注意不要误读成“B减树”。一棵 m 阶m 2的 B 树是一棵平衡的 M 路平衡搜索树可以是空树或者满足以下性质根节点至少有两个孩子每个分支节点都包含k − 1 k-1k−1个关键字和k kk个孩子其中⌈ m / 2 ⌉ ≤ k ≤ m \lceil m/2 \rceil \le k \le m⌈m/2⌉≤k≤mceil是向上取整函数每个叶子节点都包含k − 1 k-1k−1个关键字其中⌈ m / 2 ⌉ ≤ k ≤ m \lceil m/2 \rceil \le k \le m⌈m/2⌉≤k≤m所有的叶子节点都在同一层每个节点中的关键字从小到大排列节点当中k − 1 k-1k−1个元素正好是k kk个孩子包含的元素的值域划分每个结点的结构为( n , A 0 , K 1 , A 1 , K 2 , A 2 , … , K n , A n ) (n, A_0, K_1, A_1, K_2, A_2, \ldots, K_n, A_n)(n,A0​,K1​,A1​,K2​,A2​,…,Kn​,An​)。其中K i ( 1 ≤ i ≤ n ) K_i(1 \le i \le n)Ki​(1≤i≤n)为关键字且K i K i 1 ( 1 ≤ i ≤ n − 1 ) K_i K_{i1}(1 \le i \le n-1)Ki​Ki1​(1≤i≤n−1)A i ( 0 ≤ i ≤ n ) A_i(0 \le i \le n)Ai​(0≤i≤n)为指向子树根结点的指针且A i A_iAi​所指子树所有结点中的关键字均小于K i 1 K_{i1}Ki1​。n nn为结点中关键字的个数满足⌈ m / 2 ⌉ − 1 ≤ n ≤ m − 1 \lceil m/2 \rceil - 1 \le n \le m - 1⌈m/2⌉−1≤n≤m−1。3. B-树的插入分析为了简单起见假设M 3 M 3M3即三叉树。每个节点中存储两个数据两个数据可以将区间分割成三个部分因此节点应该有三个孩子。为了后续实现简单起见节点的结构如下注意孩子永远比数据多一个。用序列{53, 139, 75, 49, 145, 36, 101}构建 B 树的过程如下// 参数key为待查找的元素// 返回值PNode代表找到的节点int为该元素在该节点中的位置pairPNode,intFind(constKkey){// 从根节点的位置开始查找PNode pCur_pRoot;PNode pParentNULL;size_t i0;// 节点存在while(pCur){i0;// 在该节点的值域中查找while(ipCur-_size){// 找到返回if(keypCur-_keys[i])returnpairPNode,int(pCur,i);elseif(keypCur-_keys[i])// 该元素可能在i的左边的孩子节点中break;elsei;// 继续向右查找}// 在pCur中没有找到到pCur节点的第i个孩子中查找pParentpCur;pCurpCur-_pSub[i];}// 没有找到returnpairPNode,int(pParent,-1);}插入过程总结如果树为空直接插入新节点中该节点为树的根节点树非空找待插入元素在树中的插入位置注意找到的插入节点位置一定在叶子节点中检测是否找到插入位置假设树中的key唯一即该元素已经存在时则不插入按照插入排序的思想将该元素插入到找到的节点中检测该节点是否满足 B-树的性质即该节点中的元素个数是否等于M如果小于则满足如果插入后节点不满足 B 树的性质需要对该节点进行分裂申请新节点找到该节点的中间位置将该节点中间位置右侧的元素以及其孩子搬移到新节点中将中间位置元素以及新节点往该节点的双亲节点中插入即继续步骤 4如果向上已经分裂到根节点的位置插入结束4. B-树的插入实现4.1 B-树的节点设计// M叉树即一个节点最多有M个孩子M-1个数据域// 为实现简单起见数据域与孩子域多增加一个(原因参见上文对插入过程的分析)templateclassK,intM3structBTreeNode{K _keys[M];// 存放元素BTreeNodeK,M*_pSub[M1];// 存放孩子节点注意孩子比数据多一个BTreeNodeK,M*_pParent;// 在分裂节点后可能需要继续向上插入为实现简单增加parent域size_t _size;// 节点中有效元素的个数BTreeNode():_pParent(NULL),_size(0){for(size_t i0;iM;i)_pSub[i]NULL;}};4.2 插入key的过程按照插入排序的思想插入key注意在插入key的同时可能还要插入新分裂出来的节点。void_InsertKey(PNode pCur,constKkey,PNode pSub){// 按照插入排序思想插入keyintendpCur-_size-1;while(end0){if(keypCur-_keys[end]){// 将该位置元素以及其右侧孩子往右搬移一个位置pCur-_keys[end1]pCur-_keys[end];pCur-_pSub[end2]pCur-_pSub[end1];end--;}elsebreak;}// 插入key以及新分裂出的节点pCur-_keys[end1]key;pCur-_pSub[end2]pSub;// 更新节点的双亲if(pSub)pSub-_pParentpCur;pCur-_size;}4.3 B-树的插入实现boolInsert(constKkey){// 如果树为空直接插入if(NULL_pRoot){_pRootnewNode();_pRoot-_keys[0]key;_pRoot-_size1;returntrue;}// 找插入位置如果该元素已经存在则不插入pairPNode,intretFind(key);if(-1!ret.second)returnfalse;K kkey;PNode tempNULL;PNode pCurret.first;while(true){// 将key插入到pCur所指向的节点中_InsertKey(pCur,k,temp);// 检测该节点是否满足B-树的性质如果满足则插入成功返回否则对pCur节点进行分裂if(pCur-_sizeM)returntrue;// 申请新节点tempnewNode;// 找到pCur节点的中间位置// 将中间位置右侧的元素以及孩子搬移到新节点中intmid(M1);for(size_t imid1;ipCur-_size;i){temp-_keys[temp-_size]pCur-_keys[i];temp-_pSub[temp-_size]pCur-_pSub[i];// 更新孩子节点的双亲if(pCur-_pSub[i])pCur-_pSub[i]-_pParenttemp;}// 注意孩子比关键字多搬移一个temp-_pSub[temp-_size]pCur-_pSub[pCur-_size];if(pCur-_pSub[pCur-_size])pCur-_pSub[pCur-_size]-_pParenttemp;// 更新pCur节点的剩余数据个数pCur-_size-(temp-_size1);// 如果分裂的节点为根节点重新申请一个新的根节点// 将中间位置数据以及分裂出的新节点插入到新的根节点中插入结束if(pCur_pRoot){_pRootnewNode;_pRoot-_keys[0]pCur-_keys[mid];_pRoot-_pSub[0]pCur;_pRoot-_pSub[1]temp;_pRoot-_size1;pCur-_pParenttemp-_pParent_pRoot;returntrue;}else{// 如果分裂的节点不是根节点将中间位置数据以及新分裂出的节点继续向pCur的双亲中进行插入kpCur-_keys[mid];pCurpCur-_pParent;}}returntrue;}4.4 B-树的简单验证对 B 树进行中序遍历如果能得到一个有序的序列说明插入正确。void_InOrder(PNode pRoot){if(NULLpRoot)return;for(size_t i0;ipRoot-_size;i){_InOrder(pRoot-_pSub[i]);coutpRoot-_keys[i] ;}_InOrder(pRoot-_pSub[pRoot-_size]);}4.5 B-树的性能分析对于一棵节点为N、度为M的 B-树查找和插入需要log ⁡ M − 1 N ∼ log ⁡ M / 2 N \log_{M-1}N \sim \log_{M/2}NlogM−1​N∼logM/2​N次比较。这个很好证明对于度为M的 B-树每一个节点的子节点个数为M / 2 ∼ ( M − 1 ) M/2 \sim (M-1)M/2∼(M−1)因此树的高度应该在log ⁡ M − 1 N \log_{M-1}NlogM−1​N和log ⁡ M / 2 N \log_{M/2}NlogM/2​N之间在定位到该节点后再采用二分查找的方式可以很快定位到该元素。B-树的效率是很高的对于N 62*1000000000个节点如果度M为 1024则log ⁡ M / 2 N ≤ 4 \log_{M/2}N \le 4logM/2​N≤4即在 620 亿个元素中如果这棵树的度为 1024则需要小于 4 次即可定位到该节点然后利用二分查找可以快速定位到该元素大大减少了读取磁盘的次数。4.6 B-树的删除学习 B 树的插入足够帮助我们理解 B 树的特性了如果对删除有兴趣的同学们可以参考《算法导论》的伪代码和《数据结构-殷人昆》的 C 实现代码。5. B树和B*树5.1 B树B树是 B 树的变形是在 B 树基础上优化的多路平衡搜索树。B树的规则跟 B 树基本类似但是又在 B 树的基础上做了以下几点改进优化分支节点的子树指针与关键字个数相同分支节点的子树指针p[i]指向关键字值大小在[k[i], k[i1])区间之间所有叶子节点增加一个链接指针链接在一起所有关键字及其映射数据都在叶子节点出现B树的特性所有关键字都出现在叶子节点的链表中且链表中的节点都是有序的。不可能在分支节点中命中。分支节点相当于是叶子节点的索引叶子节点才是存储数据的数据层。5.2 B*树B*树是 B树的变形在 B树的非根和非叶子节点再增加指向兄弟节点的指针。B树的分裂当一个结点满时分配一个新的结点并将原结点中 1/2 的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针。B*树的分裂当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制 1/3 的数据到新结点最后在父结点增加新结点的指针。所以B*树分配新结点的概率比 B树要低空间使用率更高。5.3 总结通过以上介绍大致将 B 树、B树、B*树总结如下B树有序数组 平衡多叉树B树有序数组链表 平衡多叉树B*树一棵更丰满的、空间利用率更高的 B树。6. B-树的应用6.1 索引B-树最常见的应用就是用来做索引。索引通俗地说就是为了方便用户快速找到所寻之物比如书籍目录可以让读者快速找到相关信息hao123 网页导航网站为了让用户能够快速找到有价值的分类网站本质上就是互联网页面中的索引结构。MySQL 官方对索引的定义为索引index是帮助 MySQL 高效获取数据的数据结构简单来说索引就是数据结构。当数据量很大时为了能够方便管理数据、提高数据查询的效率一般都会选择将数据保存到数据库。因此数据库不仅仅是帮助用户管理数据而且数据库系统还维护着满足特定查找算法的数据结构这些数据结构以某种方式引用数据这样就可以在这些数据结构上实现高级查找算法该数据结构就是索引。6.2 MySQL索引简介MySQL 是目前非常流行的开源关系型数据库不仅是免费的可靠性高速度也比较快而且拥有灵活的插件式存储引擎如下MySQL 中索引属于存储引擎级别的概念不同存储引擎对索引的实现方式是不同的。注意索引是基于表的而不是基于数据库的。6.2.1 MyISAMMyISAM 引擎是 MySQL 5.5.8 版本之前默认的存储引擎不支持事务支持全文检索使用 BTree 作为索引结构叶节点的data域存放的是数据记录的地址其结构如下上图是以Col1为主键MyISAM 的示意图可以看出MyISAM 的索引文件仅仅保存数据记录的地址。在 MyISAM 中主索引和辅助索引Secondary key在结构上没有任何区别只是主索引要求key是唯一的而辅助索引的key可以重复。如果想在Col2上建立一个辅助索引则此索引的结构如下图所示同样也是一棵 BTreedata域保存数据记录的地址。因此MyISAM 中索引检索的算法为首先按照 BTree 搜索算法搜索索引如果指定的Key存在则取出其data域的值然后以data域的值为地址读取相应数据记录。MyISAM 的索引方式也叫做“非聚集索引”。6.2.2 InnoDBInnoDB 存储引擎支持事务其设计目标主要面向在线事务处理的应用从 MySQL 数据库 5.5.8 版本开始InnoDB 存储引擎是默认的存储引擎。InnoDB 支持 B树索引、全文索引、哈希索引。但 InnoDB 使用 BTree 作为索引结构时具体实现方式却与 MyISAM 截然不同。第一个区别是InnoDB 的数据文件本身就是索引文件。MyISAM 索引文件和数据文件是分离的索引文件仅保存数据记录的地址。而 InnoDB 索引表数据文件本身就是按 BTree 组织的一个索引结构这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键因此 InnoDB 表数据文件本身就是主索引。上图是 InnoDB 主索引同时也是数据文件的示意图可以看到叶节点包含了完整的数据记录这种索引叫做聚集索引。因为 InnoDB 的数据文件本身要按主键聚集所以 InnoDB 要求表必须有主键MyISAM 可以没有如果没有显式指定则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键如果不存在这种列则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键这个字段长度为 6 个字节类型为长整型。第二个区别是InnoDB 的辅助索引data域存储相应记录主键的值而不是地址所有辅助索引都引用主键作为data域。聚集索引这种实现方式使得按主键的搜索十分高效但是辅助索引搜索需要检索两遍索引首先检索辅助索引获得主键然后用主键到主索引中检索获得记录。