BTree

目录一、常见的搜索结构二、B树概念三、B树的插入分析四、B树的实现4.1 B树的节点设计4.2 插入key的过程4.3 B树的插入实现4.4 B树的简单验证4.5 B树的删除4.5.1 删除364.5.2 删除404.5.3 删除494.5.4 删除1504.5.5 删除1804.5.6 删除1604.5.7 删除1484.6 B树的性能分析五. B树5.1 B树的插入和分裂过程5.1.1 插入535.1.2 插入139和755.1.3 插入495.1.4 插入1455.1.5 插入365.1.6 插入1015.1.7 插入150和155六. B*树七、总结八、B树的应用8.1 索引8.2 MySQL索引简介8.2.1 B树索引的底层物理结构8.2.2 MyISAM8.2.3 InnoDB附录代码笔记一、常见的搜索结构种类数据格式时间复杂度顺序查找无要求O(N)二分查找有序O(log2Nlog2​N)二叉搜索树无要求O(N)二叉平衡树(AVL树和红黑树)无要求O(log2Nlog2​N)哈希无要求O(1)以上结构适合用于数据量相对不是很大能够一次性存放在内存中进行数据查找的场景。如果数据量很大比如有100G数据无法一次放进内存中那就只能放在磁盘上了如果放在磁盘上有需要搜索某些数据那么如果处理呢那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中那么要访问数据时先取这个地址去磁盘访问数据。使用平衡二叉树搜索树的缺陷平衡二叉树搜索树的高度是logN这个查找次数在内存中是很快的。但是当数据都在磁盘中时访问磁盘速度很慢在数据量很大时logN次的磁盘访问是一个难以接受的结果。使用哈希表的缺陷哈希表的效率很高是O(1)但是一些极端场景下某个位置冲突很多导致访问次数剧增也是难以接受的。那如何加速对数据的访问呢提高IO的速度(SSD相比传统机械硬盘快了不少但是还是没有得到本质性的提升)降低树的高度---多叉树平衡树二、B树概念1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树称为B树(后面有一个B的改进版本B树然后有些地方的B树写的的是B-树注意不要误读成B减树)。一棵m阶(m2)的B树是一棵平衡的M路平衡搜索树可以是空树或者满足一下性质根节点至少有两个孩子每个分支节点都包含k-1个关键字和k个孩子其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数每个叶子节点都包含k-1个关键字其中 ceil(m/2) ≤ k ≤ m所有的叶子节点都在同一层每个节点中的关键字从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域划分每个结点的结构为nA0K1A1K2A2… KnAn其中Ki(1≤i≤n)为关键字且KiKi1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki1。n为结点中关键字的个数满足ceil(m/2)-1≤n≤m-1。三、B树的插入分析为了简单起见假设M 3. 即三叉树每个节点中存储两个数据两个数据可以将区间分割成三个部分因此节点应该有三个孩子为了后续实现简单期间节点的结构如下多开一个是为了方便的后续操作。注意孩子永远比数据多一个。用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下插入过程总结1. 如果树为空直接插入新节点中该节点为树的根节点2. 树非空找待插入元素在树中的插入位置(注意找到的插入节点位置一定在叶子节点中)3. 检测是否找到插入位置(假设树中的key唯一即该元素已经存在时则不插入)4. 按照插入排序的思想将该元素插入到找到的节点中5. 检测该节点是否满足B树的性质即该节点中的元素个数是否等于M如果小于则满足6. 如果插入后节点不满足B树的性质需要对该节点进行分裂申请新节点找到该节点的中间位置将该节点中间位置右侧的元素以及其孩子搬移到新节点中将中间位置元素以及新节点往该节点的双亲节点中插入即继续47. 如果向上已经分裂到根节点的位置插入结束四、B树的实现4.1 B树的节点设计// M叉树即一个节点最多有M个孩子M-1个数据域 // 为实现简单期间数据域与孩子与多增加一个 templateclass K,size_t M struct BTreeNode { // 为了方便插入以后再分裂,多给一个空间 K _keys[M];// 存放元素 BTreeNodeK, M* _subs[M 1];// 存放孩子节点注意孩子比数据多一个 BTreeNodeK, M* _parent;// 在分裂节点后可能需要继续向上插入为实现简单增加parent域 size_t _size;// 记录实际存储多少个关键字 BTreeNode() { for (size_t i 0; i M; i) { _keys[i] K(); _subs[i] nullptr; } _subs[M] nullptr; _parent nullptr; _size 0; } };4.2 插入key的过程// 在node节点中插入一个key关键字和一个child孩子 void insertKey(Node* node, const K key, Node* child) { int end node-_size - 1; while (end 0) { if (key node-_keys[end]) { // 将end位置的值放到end1位置 // 挪动关键字 node-_keys[end 1] node-_keys[end]; // 挪动孩子 node-_subs[end 2] node-_subs[end 1]; end--; } else break; } // 插入key以及新分裂出来的节点 node-_keys[end 1] key; node-_subs[end 2] child; // 更新节点的双亲 if (child) child-_parent node; node-_size; }4.3 B树的插入实现bool insert(const K key) { // 如果树为空,直接申请节点插入 if (_root nullptr) { _root new Node; _root-_keys[0] key; _root-_size; return true; } std::pairNode*, int ret find(key); if (ret.second 0) { // 找到了,返回false // 不允许冗余,如果想要实现冗余,可以实现multi版本 return false; } // 没找到,但是带回了要插入节点的指针 Node* cur ret.first; K newKey key; Node* child nullptr; while (1) { // 将newKey插入cur所指向的节点中 insertKey(cur, newKey, child); // 满了就要分裂,没有满,插入就结束 if (cur-_size M) { return true; } // 计算出中位数 int mid cur-_size / 2; // 创建一个兄弟节点 Node* brother new Node; // 将cur中一半的值拷贝给兄弟节点 int index 0; size_t i mid 1; for (; i M; i) { // 分裂拷贝key和key的左孩子 brother-_keys[index] cur-_keys[i]; brother-_subs[index] cur-_subs[i]; if (cur-_subs[i]) cur-_subs[i]-_parent brother; index; // 拷贝走走后重置一下,方便观察 cur-_keys[i] K(); cur-_subs[i] nullptr; } // 还有最后一个孩子要拷 brother-_subs[index] cur-_subs[i]; if (cur-_subs[i]) cur-_subs[i]-_parent brother; cur-_subs[i] nullptr; brother-_size index; cur-_size - index 1;//因为还要提取一个中位数给父亲 K midKey cur-_keys[mid]; cur-_keys[mid] K(); // 如果cur的parent是空,则说明刚刚分裂的是根节点 if (cur-_parent nullptr) { // new一个新的根节点 _root new Node; _root-_keys[0] midKey; _root-_subs[0] cur; _root-_subs[1] brother; _root-_size 1; cur-_parent _root; brother-_parent _root; break; } else { // 转换成往cur的panrent去插入cur-_keys[mid]和brother // 如果分裂的节点不是根节点将中间位置数据以及新分裂出的节点继续向pCur的双亲中进行插入 newKey midKey; child brother; cur cur-_parent; } } return true; }4.4 B树的简单验证对B树进行中序遍历如果能得到一个有序的序列说明插入正确。void _inorder(Node* cur) { if (cur nullptr) return; size_t i 0; for (;i cur-_size; i) { _inorder(cur-_subs[i]); std::cout cur-_keys[i] ; } _inorder(cur-_subs[i]); } void inorder() { _inorder(_root); }4.5 B树的删除4.5.1 删除36把40往前挪动即可。4.5.2 删除40不是把40删了,把这个节点干掉,这样不对,首先去父亲和兄弟里面去借,只要父亲和兄弟中的值的个数大于m/2-1就可以借出来。把父亲的49借下来,然后将兄弟的53提到父亲上去,然后兄弟的55往前挪。几点数量小于m/2-1则优先找父亲借,父亲找兄弟借。4.5.3 删除49找父亲和兄弟借不到节点了,再借他们也不满足条件(m/2-1)了,那就再往上借。干掉49之后那么把父亲的53拿下来这个时候父亲就不满足条件了父亲再去借借爷爷的75拿下来可是这个时候直接把75放到父亲的节点就不对了需要和兄弟的55交换55放到父亲75放到兄弟这个时候就满足搜索树的条件了然后爷爷又不满足条件了去叔叔借把139放到爷爷位置那么这个时候叔叔的150不能往前挪因为他还有孩子所有叔叔再去把自己空缺位置的右边孩子借值借145然后叔叔空缺位置的有孩子的148往前挪这个时候正课树就都符合条件了4.5.4 删除150删除150之后孩子和关键字的数量对不上,那么又要去孩子借,借右孩子的160然后右孩子的150往前挪。4.5.5 删除180这个时候借无可借,就可以合并了干掉180及节点,那么这个时候孩子和关键字数量就不匹配了,所以问要把最右边的关键字给孩子。4.5.6 删除160直接删除即可,没啥问题。4.5.7 删除148先去借,将父亲的145借下来,然后父亲再去借爷爷的139,爷爷借无可借,那么叔叔和父亲就可以合并了,这个时候关键字和孩子对不上,那么就继续合并。4.6 B树的性能分析对于一棵节点为N度为M的B-树查找和插入需要次比较这个很好证明对于度为M的B-树每一个节点的子节点个数为\(M/2\) ~(M-1)之间因此树的高度应该在要和之间在定位到该节点后再采用二分查找的方式可以很快的定位到该元素。B树的效率是很高的对于N 62*1000000000个节点如果度M为1024则即在620亿个元素中如果这棵树的度为1024则需要小于4次即可定位到该节点然后利用二分查找可以快速定位到该元素大大减少了读取磁盘的次数。五. B树B树是B树的变形是在B树基础上优化的多路平衡搜索树B树的规则跟B树基本类似但是又在B树的基础上做了以下几点改进优化分支节点的子树指针与关键字个数相同分支节点的子树指针p[i]指向关键字值大小在[k[i]k[i1])区间之间所有叶子节点增加一个链接指针链接在一起所有关键字及其映射数据都在叶子节点出现分支节点跟叶子几点有重复的值,分支节点存的是叶子节点索引,父亲中存的是孩子节点中的最小值做索引。分支节点只存key叶子节点存key/value。B树的特性所有关键字都出现在叶子节点的链表中且链表中的节点都是有序的。不可能在分支节点中命中。分支节点相当于是叶子节点的索引叶子节点才是存储数据的数据层。5.1 B树的插入和分裂过程B树的插入过程跟B树基本是类似的,细节区别在于,第一次插入两层节点,一层做分支,一层做根,后面一样,往叶子去插入,插入满了以后,分裂一半给兄弟,转换成往父亲插入一个key和一个孩子,孩子就是兄弟,key是兄弟的第一个最小值的key。插入{53139754914536101150155}M3的B树分裂过程5.1.1 插入535.1.2 插入139和755.1.3 插入49插入49后要产生第一次分裂。创建一个兄弟节点,拷一半给兄弟,并且把兄弟的第一个最小值插入到根节点中。5.1.4 插入1455.1.5 插入36插入36后,根节点的最小值也要变化。5.1.6 插入101插入101之后,产生第二次分裂。创建兄弟节点,拷贝一半给兄弟,然后将兄弟节点中的最小值插入到根节点。5.1.7 插入150和155插入150之后没啥影响。插入155之后需要分裂。创建兄弟节点,拷贝一半给兄弟,将兄弟节点中的最小值插入到根节点根节点也满了,继续分裂。创建兄弟节点,拷贝一半给兄弟,然后创建新的根,保存两个节点中的第一个最小值的key。最后将所有的节点全部链接起来方便遍历。总结简化B树孩子比关键字多一个的规则,变成相等。所有值都在叶子上,方便遍历查找所有值。六. B*树B*树是B树的变形在B树的非根和非叶子节点再增加指向兄弟节点的指针。本质是想提高空间的利用率真正的优化是让空间利用率更高。B树的分裂当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针。B*树的分裂B*树的节点关键字和孩子数量-[2/3*M,M]当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针。所以B*树分配新结点的概率比B树要低空间使用率更高七、总结通过以上介绍大致将B树B树B*树总结如下B树有序数组平衡多叉树B树有序数组链表平衡多叉树B*树一棵更丰满的空间利用率更高的B树。八、B树的应用在内存中,做内查找,B树系列和哈希表和平衡树对比单纯论树高度,搜索效率而言,B树确实不错,但是B树有一些隐形坏处空间利用率低消耗高插入和删除数据时,分裂和合并节点,那么必然挪动给数据虽然高度更低,但是在内存中而言,跟哈希和平衡树还是一个量级,B树是,平衡树是,哈希是O(1)其实都是一个量级结论实质上B树系列在内存中体现不出优势。B树假设M1024N10亿也就是三次。平衡搜索树N10亿,也就三十次。内存中搜索3次和30次差别不是特别大,磁盘中搜索3次和30次差别巨大。8.1 索引B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物比如书籍目录可以让读者快速找到相关信息hao123网页导航网站为了让用户能够快速的找到有价值的分类网站本质上就是互联网页面中的索引结构。MySQL官方对索引的定义为索引(index)是帮助MySQL高效获取数据的数据结构简单来说索引就是数据结构。当数据量很大时为了能够方便管理数据提高数据查询的效率一般都会选择将数据保存到数据库因此数据库不仅仅是帮助用户管理数据而且数据库系统还维护着满足特定查找算法的数据结构这些数据结构以某种方式引用数据这样就可以在这些数据结构上实现高级查找算法该数据结构就是索引。8.2 MySQL索引简介mysql是目前非常流行的开源关系型数据库不仅是免费的可靠性高速度也比较快而且拥有灵活的插件式存储引擎如下数据库引擎MyISAM和InnoDB用的都是B树。MEMORY引擎默认使用的就是哈希索引。InnoDB是比较新一点的数据库引擎,MyISAM是比较老一点的数据库引擎,现在建数据库用的都是InnoDB引擎,MyISAM不支持事务。MySQL中索引属于存储引擎级别的概念不同存储引擎对索引的实现方式是不同的。注意索引是基于表的,而不是基于数据库的。8.2.1B树索引的底层物理结构一般数据库要求主键是唯一的比如mysql。建表的主键,就是B树的keyB树的value是存储一行数据的磁盘地址分支节点也是需要存到磁盘中的因为数据量大了,内存是存不下的,分支节点中应该是磁盘地址,但是分支节点理论应该尽量被缓存到cache。假设我有如下sql语句正好对应的是上面的表。CREATE TABLE StuInfo ( stuID int, age int, name varchar(255), address varchar(255), city varchar(255), .... PRIMARY KEY(stuID) ) ENGINEINNODB DEFAULT CHARSETutf8假设我想将Rose的年龄改为35,那么有以下两种写法UPDATE StuInfo SET age 35 WHERE stuID 50; UPDATE StuInfo SET age 35 WHERE name Rose;第一个写法效率高,第二个写法效率低,因为用的是sutID做的索引,这个主键stuID是索引,主键也就是B树中的key。第一个可以使用B树进行查找,效率高。第二个只能遍历B树所有叶子节点,暴力查找,效率低 O(N)。数据库中能用主键查找就去用主键查找如果经常想使用name去进行查找怎么办可以用name创建一个索引。类似于上图。语句CREATE INDEX nameindex ON StuInfo(name)对name创建索引后,相当于使用B树用name做key创建一棵树当然,value只想磁盘数据,再执行sql语句,效率就提高了。UPDATE StuInfo SET age 35 WHERE name Rose;一般数据库要求主键是不重复唯一字段电话、身份证号码适合名字、地址不合适如果没有字段能保持唯一可以考虑自增主键其实他自己建立一个自增数做主键般数据库不要求索引唯一像mysql建立索引可以考虑使用B树或者hash表数据结构允许冗余。如果用名字做主键,冲突了怎么办INSERT INTO Studinfo(name,id,age) VALUES (张伟,1,18); INSERT INTO Studinfo(name,id,age) VALUES (张伟,2,20);插入第二条语句直接就会报错,主键张伟已经存在。B树做主键索引相比B树的优势B树所有值都在叶子,遍历很方便,方便区间查找对于没有建立索引的字段,全表扫描的遍历很方便分支节点只存key,一个分支节点空间占用较小,可以尽可能的加载到缓存B树不用到叶子就能找到值,B树一定要到叶子,这是B树一个优势,但是B树高度足够低,所以差别不大8.2.2 MyISAMMyISAM引擎是MySQL5.5.8版本之前默认的存储引擎不支持事务最大硬伤支持全文检索一种搜索技术,倒排索引使用BTree作为索引结构叶节点的data域存放的是数据记录的地址方便索引树和主键树映射同样的数据其结构如下索引文件中存的是数据文件地址。上图是以id为主键MyISAM的示意图可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中主索引和辅助索引Secondary key在结构上没有任何区别只是主索引要求key是唯一的而辅助索引的key可以重复。如果想在age上建立一个辅助索引则此索引的结构如下图所示同样也是一棵BTreedata域保存数据记录的地址。因此MyISAM中索引检索的算法为首先按照BTree搜索算法搜索索引如果指定的Key存在则取出其data域的值然后以data域的值为地址读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”的。8.2.3 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域。先用namename对应主键id,再用主键id再去主键树搜索一次也就是说他用索引查找要查找两次。聚集索引这种实现方式使得按主键的搜索十分高效但是辅助索引搜索需要检索两遍索引首先检索辅助索引获得主键然后用主键到主索引中检索获得记录。附录代码HighOrderDataStruct: B树、并查集、图、LRU Cache、跳表 - Gitee.comhttps://gitee.com/Axurea/high-order-data-struct/tree/master/2026_10_28_BTree笔记2026_10_16_B树.png · Aurora/HighOrderDataStruct - Gitee.comhttps://gitee.com/Axurea/high-order-data-struct/blob/master/2026_10_16_B%E6%A0%91.png