目录

一、常见的搜索结构

二、B树概念

三、B树的插入分析

四、B树的实现

4.1 B树的节点设计

4.2 插入key的过程

4.3 B树的插入实现

4.4 B树的简单验证

4.5 B树的删除

4.5.1 删除36

4.5.2 删除40

4.5.3 删除49

4.5.4 删除150

4.5.5 删除180

4.5.6 删除160

4.5.7 删除148

4.6 B树的性能分析

五. B+树

5.1 B+树的插入和分裂过程

5.1.1 插入53

5.1.2 插入139和75

5.1.3 插入49

5.1.4 插入145

5.1.5 插入36

5.1.6 插入101

5.1.7 插入150和155

六. B*树

七、总结

八、B树的应用

8.1 索引

8.2 MySQL索引简介

8.2.1 B+树索引的底层物理结构

8.2.2 MyISAM

8.2.3 InnoDB

附录

代码

笔记

一、常见的搜索结构

以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘上，有需要搜索某些数据，那么如果处理呢？那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据。

使用平衡二叉树搜索树的缺陷：

平衡二叉树搜索树的高度是logN，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，访问磁盘速度很慢，在数据量很大时，logN次的磁盘访问，是一个难以接受的结果。

使用哈希表的缺陷：

哈希表的效率很高是O(1)，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难以接受的。

那如何加速对数据的访问呢？

1. 提高IO的速度(SSD相比传统机械硬盘快了不少，但是还是没有得到本质性的提升)
2. 降低树的高度---多叉树平衡树

二、B树概念

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(后面有一个B的改进版本B+树，然后有些地方的B树写的的是B-树，注意不要误读成"B减树")。一棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

1. 根节点至少有两个孩子
2. 每个分支节点都包含k-1个关键字和k个孩子，其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数
3. 每个叶子节点都包含k-1个关键字，其中 ceil(m/2) ≤ k ≤ m
4. 所有的叶子节点都在同一层
5. 每个节点中的关键字从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分
6. 每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An）其中，Ki(1≤i≤n)为关键字，且Ki<Ki+1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。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树的性质，需要对该节点进行分裂：
申请新节点
找到该节点的中间位置
将该节点中间位置右侧的元素以及其孩子搬移到新节点中
将中间位置元素以及新节点往该节点的双亲节点中插入，即继续4

7. 如果向上已经分裂到根节点的位置，插入结束

四、B树的实现

4.1 B树的节点设计

// M叉树：即一个节点最多有M个孩子，M-1个数据域 // 为实现简单期间，数据域与孩子与多增加一个 template<class K,size_t M> struct BTreeNode { // 为了方便插入以后再分裂,多给一个空间 K _keys[M];// 存放元素 BTreeNode<K, M>* _subs[M + 1];// 存放孩子节点，注意：孩子比数据多一个 BTreeNode<K, 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位置的值放到end+1位置 // 挪动关键字 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::pair<Node*, 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树的基础上做了以下几点改进优化：

1. 分支节点的子树指针与关键字个数相同
2. 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
3. 所有叶子节点增加一个链接指针链接在一起
4. 所有关键字及其映射数据都在叶子节点出现

分支节点跟叶子几点有重复的值,分支节点存的是叶子节点索引,父亲中存的是孩子节点中的最小值做索引。

分支节点只存key，叶子节点存key/value。

B+树的特性：

1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
2. 不可能在分支节点中命中。
3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。

5.1 B+树的插入和分裂过程

B+树的插入过程跟B树基本是类似的,细节区别在于,第一次插入两层节点,一层做分支,一层做根,后面一样,往叶子去插入,插入满了以后,分裂一半给兄弟,转换成往父亲插入一个key和一个孩子,孩子就是兄弟,key是兄弟的第一个最小值的key。

插入{53，139，75，49，145，36，101，150，155}，M==3的B树分裂过程

5.1.1 插入53

5.1.2 插入139和75

5.1.3 插入49

插入49后要产生第一次分裂。

创建一个兄弟节点,拷一半给兄弟,并且把兄弟的第一个最小值插入到根节点中。

5.1.4 插入145

5.1.5 插入36

插入36后,根节点的最小值也要变化。

5.1.6 插入101

插入101之后,产生第二次分裂。

创建兄弟节点,拷贝一半给兄弟,然后将兄弟节点中的最小值插入到根节点。

5.1.7 插入150和155

插入150之后没啥影响。

插入155之后需要分裂。

创建兄弟节点,拷贝一半给兄弟,将兄弟节点中的最小值插入到根节点，根节点也满了,继续分裂。

创建兄弟节点,拷贝一半给兄弟,然后创建新的根,保存两个节点中的第一个最小值的key。

最后将所有的节点全部链接起来，方便遍历。

总结：

1. 简化B树孩子比关键字多一个的规则,变成相等。
2. 所有值都在叶子上,方便遍历查找所有值。

六. 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树有一些隐形坏处：

1. 空间利用率低，消耗高
2. 插入和删除数据时,分裂和合并节点,那么必然挪动给数据
3. 虽然高度更低,但是在内存中而言,跟哈希和平衡树还是一个量级,B树是,平衡树是,哈希是O(1)，其实都是一个量级

结论：实质上B树系列在内存中体现不出优势。

B树：，假设M=1024，N=10亿，也就是三次。

平衡搜索树：，N=10亿,也就三十次。

内存中搜索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+树的key，B+树的value是存储一行数据的磁盘地址，分支节点也是需要存到磁盘中的，因为数据量大了,内存是存不下的,分支节点中应该是磁盘地址,但是分支节点理论应该尽量被缓存到cache。

假设我有如下sql语句，正好对应的是上面的表。

CREATE TABLE StuInfo ( stuID int, age int, name varchar(255), address varchar(255), city varchar(255), .... PRIMARY KEY(stuID) ) ENGINE=INNODB DEFAULT CHARSET=utf8

假设我想将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树的优势

1. B+树所有值都在叶子,遍历很方便,方便区间查找
2. 对于没有建立索引的字段,全表扫描的遍历很方便
3. 分支节点只存key,一个分支节点空间占用较小,可以尽可能的加载到缓存

B树不用到叶子就能找到值,B+树一定要到叶子,这是B树一个优势,但是B+树高度足够低,所以差别不大

8.2.2 MyISAM

MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事务（最大硬伤），支持全文检索（一种搜索技术,倒排索引），使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址（方便索引树和主键树映射同样的数据），其结构如下：

索引文件中存的是数据文件地址。

上图是以id为主键，MyISAM的示意图，可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果想在age上建立一个辅助索引，则此索引的结构如下图所示：

同样也是一棵B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”的。

8.2.3 InnoDB

InnoDB存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从MySQL数据库5.5.8版本开始，InnoDB存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但InnoDB使用B+Tree作为索引结构时，具体实现方式却与MyISAM截然不同。

第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而InnoDB索引，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录，这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

第二个区别是InnoDB的辅助索引data域存储相应记录主键的值而不是地址,所有辅助索引都引用主键作为data域。

先用name，name对应主键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