- 综合排序
- 最热优先
- 最新优先
- 来自专栏用户4352451的专栏
B+树
三、B+树 B+树是B-树的变体，也是一种多路搜索树，其定义基本与B树相同，除了： 非叶子结点的子树指针与关键字个数相同； 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1 四、B树与B+树的对比 B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。 2、B+树的优点 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。 因此访问叶子几点上关联的数据也具有更好的缓存命中率； B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。 相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。 3、应用 B树和B+树经常被用于数据库中，作为MySQL数据库索引。索引（Index）是帮助MySQL高效获取数据的数据结构。
69620发布于 2020-08-26 - 来自专栏CSDN搜“看，未来”
浅谈 B+树
目前常见的主要的三种存储引擎是：哈希、B+树、LSM树。LSM下次再说，hash讲过了。 没有什么B-树，那是 B-tree，国内一直翻译成B-树，其实就是B树。 B树我也不想说了，因为已经被升级过了，叫B+树。 下图来自 小灰的算法之旅，懂得人自然就懂了： ---- 对比一下B树： 这个是B树。 ---- B+树对于B树的改进 1、所有数据都在叶子节点。算法更容易理解了。回头抽空手写一下B+树，正好跳表也要重写了。 2、底层叶子节点使用链表串起来了。 这第二个改进不可谓不秀。 单这么看自然是不明所以的，但是凡事都要放在上下文中去看，B+树的上下文对应的就是磁盘IO的索引呐，那如果我要范围查询呢？比如说我要上面树里面 4-10 的所有数据，B 树怎么作为？B+树怎么作为？
52420发布于 2021-10-09 - 来自专栏烟草的香味
B+树，索引树
引言 时隔一年，我又想起当初看数据库时，看到的B+树，就是数据库的索引使用的数据结构。再整理一下，看看自己没有忘记很多吧。 概述 B+树之前，先来看一下二叉查找树（1,2,3,4,5,6,7） ? 那么B+树是如何解决这个问题的呢？ 试想一下，区间查找比较高效的数据结构是什么？数组，只要找到id为10的元素下标，那么之后的所有就都符合了。 没错，这就是B+树。 这个结构是怎么想出来的我不知道啊，但是我今天突然发现，他的存储方式和跳表十分之像啊。莫非是受到了跳表的启发？亦或是跳表受到了B+树的启发？咱也不知道。 引申 很好，B+树整明白了，新的问题出现了。如果数据库使用这种数据结构存储，全部放到内存中肯定是不现实的，势必要将其存储到硬盘中，待查找时再到文件中读取。 B+树是不是分叉越多越好 那肯定不是越多越好啊，要是一层就把所有数据都存储了，要他还有什么用，根本没有起到快速定位的作用。 但我想说的并不是这。
1.2K20发布于 2019-12-02 - 来自专栏社区的朋友们
理解 B+ 树算法
B+ 树主要价值在于存储用于在面向块的存储环境中高效检索的数据，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。 B+ 树元素自底向上插入。 另外说明的一点，B+中的B并不是代表二叉(Binary),而是代表平衡(Balance)。 对于m阶B+树，m的值越大，固定高度的B+树存放的值就越多。 B+树的内部结点并没有指向关键字具体信息的指针。 而B+树内部结点只需要1个盘块。当需要把内部结点读入内存中的时候，B 树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转寻道的时间)。
3.1K00发布于 2017-10-20 - 来自专栏性能与架构
mysql B+树索引
上图就是一棵B+树，每个部分有3个主要概念：物理磁盘块、数据项(蓝色)、指针(红色) 如磁盘块1，包含数据项 17、35，包含指针 P1、P2、P3，P1指向小于17的磁盘块，P2指向在17和35之间的磁盘块 真实的数据存于叶子节点中，即 3、5、9、10、13、15、28、29、36、60、75、79、90、99 非叶子节点中并不存放真实数据项，只存放指引搜索方向的数据项，如 17、35 并不真实存在于数据表中 B+ 内存中做二分查找找到29，结束查询 总计三次IO，即可找到目标数据项 3层的B+树可以表示上百万的数据，对查询性能的提高是巨大的
1.1K80发布于 2018-04-02 - 来自专栏面试
B+树的结构
阶数与节点容量B+树的阶数m决定了节点的子节点数量和键值容量，通常与磁盘页大小对齐以优化I/O 非根节点：键值数范围：⌈m/2⌉−1≤k≤m−1⌈m/2⌉−1≤k≤m−1（如3阶B+树，非根节点最多2个键值 与B树的区别B+树在以下方面区别于B树 数据存储位置：B树内部节点存数据，B+树仅叶子节点存数据。链表结构：B+树叶子节点通过链表连接，B树无此设计。 查询稳定性：B+树查询必须到叶子节点，路径固定；B树可能在内部节点提前终止查询。5. 而对于高度为3的B+树(21902400 条数据)就可以存放 1170 x 1170 x 16 = 21902400 条数据（两千多万条数据），也就是对于两千多万条的数据，为什么索引结构默认使用B+树， B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更矮壮，也是就说，相同的数据量，B+树数据结构，查询磁盘的次数会更少。
79310编辑于 2025-03-18 - 来自专栏技术教程
MySQL索引B+树详解
下面是对 MySQL 索引 B+ 树的详细解析： B+ 树的核心设计目标适配磁盘存储： 磁盘 I/O（读取/写入数据块）是数据库操作的主要性能瓶颈。 B+ 树设计成每个节点大小通常等于一个磁盘页（如 16KB），最大化每次 I/O 读取的数据量。降低树高度： B+ 树是一个“矮胖”的多叉树。 二、 B+ 树的结构详解（以 InnoDB 为例）一棵典型的 B+ 树包含以下几种节点：根节点 (Root Node):树的顶端节点。 五、 B+ 树在 MySQL InnoDB 中的具体实现聚簇索引 (Clustered Index):表数据按照主键顺序物理存储在 B+ 树的叶子节点中。 查找过程需要两次 B+ 树搜索：在辅助索引 B+ 树中找到主键值。用该主键值在聚簇索引 B+ 树中查找完整的行数据（回表）。
97320编辑于 2025-07-02 - 来自专栏IT当时语_青山师_JAVA技术栈
B树、B+树的区别及MySQL为何选择B+树
B树、B+树的区别及MySQL为何选择B+树 1. B树和B+树的定义 B树和B+树都是一种多路搜索树，常用于数据库和文件系统中进行索引操作。在介绍B树和B+树的区别之前，先来了解一下它们的定义。 B+树 B+树也是一种多路搜索树，与B树相似，但在B+树中，所有的数据都存储在叶子节点中，而非在非叶子节点中。B+树满足以下条件： 所有关键字都出现在叶子节点的链表中，且链表中的关键字恰好是有序的。 B树和B+树的区别 B树和B+树虽然都是多路搜索树，但它们的区别还是比较明显的。 存储结构 B树的非叶子节点中既包含索引，也包含数据，而B+树的非叶子节点中只包含索引，数据都存储在叶子节点中。 查询性能 B+树的查询性能更优，因为B+树的数据都存储在叶子节点中，而B树的数据既可能存储在非叶子节点中，也可能存储在叶子节点中。 MySQL采用的是B+树作为索引的数据结构，原因如下： B+树的查询性能更好，因为数据都存储在叶子节点中，查询时只需要遍历一次叶子节点即可得到查询结果。
2.1K10编辑于 2023-05-05 - 来自专栏宇宙之_一粟
B树和B+树
B树和B+树都是用于外查找的数据结构，都是平衡多路查找树。 两者的区别 在B+树中，具有n个关键字的结点含有n棵子树，即每个关键字对应一颗子树；而在B树中，具有n个关键字的结点含有(n+1)棵子树。 在B+树中，除根节点外，每个结点中的关键字个数n的取值范围是[m/2]~m，根节点n的取值范围是2~m；而在B树中，除根节点外，其他所有非叶结点的关键字个数n的取值范围是[m/2]-1~m-1，根节点n B+树中的所有叶结点包含了全部关键字，即其他非叶结点中的关键字包含在叶结点中；而在B树中，关键字是不重复的。 B+树中的所有非叶结点仅起到索引的作用，即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不包含该关键字对应记录的存储地址；而在B树中，每个关键字对应一个记录的存储地址。 通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶结点，所有叶结点链接成一个不定长的线性链表，所以B+树可以进行随机查找和顺序查找；而B树只能进行随机查找。
1.2K41发布于 2020-10-26 - 来自专栏JMCui
MySQL 的B+树索引.
B+ 树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树，B+ 树中的 B 不是代表二叉（binary），而是代表平衡（balance）。 在 B+ 树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接，叶子节点之间组成一个双向链表。 ? B+ 树索引的本质就是 B+ 树在数据库中的实现，但是 B+ 索引在数据库中有一个特点是高扇出性（数据库分区），因此在数据库中，B+ 树的高度一般都在 2-4 层，这也就是说查找某一键值的行记录时最多只需要 数据库中的 B+ 树索引可以分为 聚集索引和辅助索引。 B+ 树索引并不能找到一个给定键值的具体行。B+ 树索引能找到的只是被查找数据行所在的页。 从本质上来说，联合索引也是一棵B+ 树。那么什么时候会使用到联合索引呢？"
1.2K20发布于 2020-08-14 - 来自专栏程序员小灰
漫画：什么是B+树？
这一次我们来介绍B+树。 ————————————————— 一个m阶的B树具有如下几个特征： 1.根结点至少有两个子女。 一个m阶的B+树具有如下几个特征： 1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。 B-树中的卫星数据（Satellite Information）： B+树中的卫星数据（Satellite Information）： 需要补充的是，在数据库的聚集索引（Clustered Index 第三次磁盘IO： B-树的范围查找过程 自顶向下，查找到范围的下限（3）： 中序遍历到元素6： 中序遍历到元素8： 中序遍历到元素9： 中序遍历到元素11，遍历结束： B+ B+树的优势： 1.单一节点存储更多的元素，使得查询的IO次数更少。 2.所有查询都要查找到叶子节点，查询性能稳定。 3.所有叶子节点形成有序链表，便于范围查询。 —————END—————
57230编辑于 2022-07-05 - 来自专栏哈哈熊
【数据结构】B+树简述
一、B+树的结构特点 1.非叶子节点仅具有索引作用，也就是说，非叶子节点只能存储Key,不能存储value 2.树的所有叶节点构成一个有序链表，可以按照key排序的次序依次遍历全部数据。 二、B+树存储数据 若参数M选择为5，那么每个节点最多包含4个键值对，我们以5阶B+树为例，看看B+树的数据存储 (a) 在空树当中插入5 （b）继续插入8，10，15 （c）继续插入16 （d）继续插入 17 （e）继续插入18 （f）继续插入6,9,19,20,21,22 (e)继续插入7 三、B+树和B树的对比 B+ 树的优点在于： 1.由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下 B树的优点在于： 由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的位置，就能找到value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次 ，都是用到了B+树来提高查询的效率；在操作数据库时，我们为了提高查询效率，可以基于某张表的某个字段建立索引，就可以提高查询效率，那其实这个索引就是B+树这种数据结构实现的。
1.3K10编辑于 2024-04-23 - 来自专栏业余草
图解B+树的插入过程
B+ 树在现代数据库中很常见，如果我们了解它，在工作中可能对性能优化会有更好的帮助！ 最近我一直在思考 B+ 树的高度是由什么决定的。知道我了解了 B+ 树的插入过程，才有一种恍然大悟的感觉！ 网上的一些资料杂乱无章，不同的数据库可能还有对 B+ 树有不同的实现。但是万变不离其宗，B+ 树的定义，大致如下所示： ? 总结一下，B+ 树有下面 5 个重要的特点。 B+ 树与 B 树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。 根据上面的特点，我们来看看 B+ 树的插入过程。 下面以一棵 5 阶 B+ 树的插入过程，5 阶 B+ 树的节点最少 2 个 key，最多 4 个 key。 1、当树为空树，插入 5。 ? 根据这个插入过程，一个 B+ 树的高度，是有一个节点能存储多少关键字，也就是索引决定的。通常，一棵 MySQL 的 B+ 树，树高为 3 的话，大约能存上亿条。树的高度太高的话，查询效率会大打折扣！
7.6K20发布于 2019-07-11 - 来自专栏java达人
LSM树 与B+树比较
这就是B+树的原理，但是写起来就很糟糕，因为会产生大量的随机IO，磁盘寻道速度跟不上。 关于b树 B+树最大的性能问题是会产生大量的随机io。随着新数据的插入，叶子节点会慢慢分裂。 例如，Oracle 的常用索引使用 B+ 树。下面是一个B+树的例子 根节点和分支节点很简单，记录每个叶子节点的最小值，用指针指向叶子节点。 与B+树相比，它牺牲了部分读取性能来提高写入性能。 其原理是将一棵大树分裂成n棵小树，先写入内存（不存在内存中的seek速度问题，所以随机写入的性能大大提高）。在内存中构建了一个有序的小树。 以上就是LSM树最本质的原理，有了原理，再看具体的技术就很简单了： 关于lsm内存结构，可以是B+树，还可以为跳跃表（skip-list）或是一个有序字符串表（SSTables）。
1.2K20编辑于 2022-05-16 - 来自专栏全栈程序员必看
B+树|MYSQL索引使用原则
一、存储引擎的比较 注：上面提到的B树索引并没有指出是B-Tree和B+Tree索引，但是B-树和B+树的定义是有区别的。 接下来我们先看看B-树、B+树的概念。弄清楚，为什么加了索引查询速度会加快？ 树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题； 由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并； B+ 树 B+树是B-树的变体，也是一种多路搜索树： 1.其定义基本与B-树同，除了： 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1] )的子树（B-树是开区间）； 5.为所有叶子结点增加一个链指针； 6.所有关键字都在叶子结点出现； 如：（M=3） B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在 非叶子结点命中
67120编辑于 2022-06-29 - 来自专栏c++与qt学习
为什么 MySQL 使用 B+ 树
为什么 MySQL 使用 B+ 树 概述 设计 读写性能 数据加载 总结 个人概括 参考 ---- 概述 首先需要澄清的一点是，MySQL 跟 B+ 树没有直接的关系，真正与 B+ 树有关系的是 MySQL 在具体分析 InnoDB 使用 B+ 树背后的原因之前，我们需要为 B+ 树找几个『假想敌』，因为如果我们只有一个选择，那么选择 B+ 树也并不值得讨论，找到的两个假想敌就是 B 树和哈希，相信这也是很多人会在面试中真实遇到的问题 ，我们就以这两种数据结构为例，分析比较 B+ 树的优点。 有些读者可能会认为使用 B+ 树这种数据结构会增加树的高度从而增加整体的耗时，然而高度为 3 的 B+ 树就能够存储千万级别的数据，实践中 B+ 树的高度最多也就 4 或者 5，所以这并不是影响性能的根本问题 ---- 参考 为什么 MySQL 使用 B+ 树 B+ Tree和B Tree
66630编辑于 2023-02-26 - 来自专栏用户画像
6.3.2 B+树基本概念
B+是应用数据库所需而出现的一种B树的变形树。 一棵B+树需满足下列条件： 1）每个分支结点最多有m棵子树（子结点）。 m阶的B+与m阶的B树的主要差异在于： 1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。 4）在B+树中，叶结点包含全部关键字，即在非叶子结点中出现的关键字也会在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。 通常在B+树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此，可以对B+树进行两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始，进行多路查找。 所以B+树中，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。
53420发布于 2018-08-24 - 来自专栏YIN_尹的博客
【高阶数据结构】B+树
B+树的概念 B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了一些改进优化。 B+树的查找 B+树的查找上面有提到——查找不可能在分支节点中命中，如果能找到，应该在叶子节点的链表中： 还是这棵B+树为例，比如我们要查找33 从根结点开始33比5大，往后走，比28也大，再往后走 那除了上面的查找方法，其实B+树还有另外一种查找方法： 上面提到对于B+树来说，所有叶子节点增加一个链接指针链接在一起 而每个叶子结点的链表里面元素都是有序的。 B-树 VS B+树 2. B+树分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层（与B树不同）。 总结： 4. B+ 树的插入分析 这里简单画一个3阶B+树插入分裂的过程图，大家可以简单看看了解一下：
34410编辑于 2024-02-21 - 来自专栏全栈程序员必看
mysql b+树优点_基础B
我：B+树 面试官：为什么要用B+树，而不是B树？ 我：… 面试官：用B+树作为MySql的索引结构，用什么好处？ 简化 B+树 如下图 因为内节点并不存储 data，所以一般B+树的叶节点和内节点大小不同，而B-树的每个节点大小一般是相同的，为一页。 为了增加 区间访问性，一般会对B+树做一些优化。 如下图带顺序访问的B+树。 B-树和B+树的区别 1.B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。 B+树： 由于B+树所有的 data 域都在根节点，所以查询 key 为 50的节点必须从根节点索引到叶节点，时间复杂度固定为 O(log n)。 这就意味着B+树单次磁盘 IO 的信息量大于B-树，从这点来看B+树相对B-树磁盘 IO 次数少。
80220编辑于 2022-11-16 mysql-innodb之B+树
B+树查找原理 查找索引页，索引页不在缓存中，则去磁盘中找到对应的索引页并放到lru队列头部 从索引页中找到对应的数据页，数据页若不在内存，也需要去磁盘加载到内存 找到对应的数据页再查询具体的数据 B+ 树相关算法和数据结构 二分查找法 将记录按有序化排列后，将查找的数据和有序队列中的中点位置的数据进行比较后排除一半数据再以此类推，查询次数一般为log2n, 比如n为10，则查询次数为3~4之间 B+树 b+树最多有m个子节点，m也被叫做b+树的最小度数， 则单个节点中的键数量范围为⌈m/2⌉-1, m-1 B+树插入分裂： 插入节点后若节点内键数 > 最大键数， 则对左节点进行分裂，将中间键值放入索引页 若分裂后导致上层索引页的键数 > 最大键数，则继续分裂索引页，索引页分裂小于中间键值的为左子树，大于的为右子树 b+树如下，m=5 ，键数量范围为 （2，4） 插入数据28， 由于28插入后，叶子节点键值为 非索引节点键值，也不需要处理索引节点 删除25，删除25后，叶子节点还剩2个键，不需要借键或者合并，叶子节点直接更新，但25也是索引节点，为了保持稳定，则需要用28替换25索引节点上的键 图片 注意 b+
34210编辑于 2025-03-13
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号