- 综合排序
- 最热优先
- 最新优先
- 来自专栏IT当时语_青山师_JAVA技术栈
B树、B+树的区别及MySQL为何选择B+树
B树、B+树的区别及MySQL为何选择B+树 1. B树和B+树的定义 B树和B+树都是一种多路搜索树，常用于数据库和文件系统中进行索引操作。在介绍B树和B+树的区别之前，先来了解一下它们的定义。 B+树 B+树也是一种多路搜索树，与B树相似，但在B+树中，所有的数据都存储在叶子节点中，而非在非叶子节点中。B+树满足以下条件： 所有关键字都出现在叶子节点的链表中，且链表中的关键字恰好是有序的。 所有的非叶子节点可以看做是索引部分，节点中仅包含子树中的最大（或最小）关键字。 2. B树和B+树的区别 B树和B+树虽然都是多路搜索树，但它们的区别还是比较明显的。 查询性能 B+树的查询性能更优，因为B+树的数据都存储在叶子节点中，而B树的数据既可能存储在非叶子节点中，也可能存储在叶子节点中。 B+树在查询时只需要遍历一次叶子节点即可得到查询结果，而B树则需要遍历非叶子节点和叶子节点，效率相对较低。 3.
2.2K10编辑于 2023-05-05 - 来自专栏用户4352451的专栏
B+树
（3）另外一方面，同样的数据，红黑树的阶数更大，B树更短，这样查找的时候当然B树更具有优势了，效率也就越高。 二、B树 对于B树，我们首先要知道它的应用，B树大量应用在数据库和文件系统当中。 B树算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。 假定一个节点可以容纳100个值，那么3层的B树可以容纳100万个数据，如果换成二叉查找树，则需要20层！ 四、B树与B+树的对比 B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。 2、B+树的优点 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。 而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。 3、应用 B树和B+树经常被用于数据库中，作为MySQL数据库索引。
71420发布于 2020-08-26 - 来自专栏烟草的香味
B+树，索引树
引言 时隔一年，我又想起当初看数据库时，看到的B+树，就是数据库的索引使用的数据结构。再整理一下，看看自己没有忘记很多吧。 概述 B+树之前，先来看一下二叉查找树（1,2,3,4,5,6,7） ? 但想想数据库查找数据的场景： select * from user where id > 10， 显然，对于这种查找区间来说，二叉查找树并不高效。那么B+树是如何解决这个问题的呢？ 没错，这就是B+树。 这个结构是怎么想出来的我不知道啊，但是我今天突然发现，他的存储方式和跳表十分之像啊。莫非是受到了跳表的启发？亦或是跳表受到了B+树的启发？咱也不知道。 算一下，如果是3叉树，高度为3（这个高度为索引树的高度），可索引的数组长度为：（3^4=81）；如果是5叉树，高度为3，可索引数组长度为：（5^4=625）；如果是100叉树，高度为3，可索引长度为：（ 索引1亿的数据量，高度也只有3，意味着只要进行3此IO就可以定位到。完美。 那树进行分叉过多，是不是在每个节点搜索子节点的效率下降了？这里可以再使用一些查找算法降低时间复杂度。
1.2K20发布于 2019-12-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树无此设计。 而对于高度为3的B+树(21902400 条数据)就可以存放 1170 x 1170 x 16 = 21902400 条数据（两千多万条数据），也就是对于两千多万条的数据，为什么索引结构默认使用B+树， 结构示意图示例（以3阶B+树为例）： [内部节点: 10, 20] / | \ [叶子: 5→9] → [叶子:10→19] → [叶子
84910编辑于 2025-03-18 - 来自专栏码农知识点
浅谈树形结构的特性和应用（上）:多叉树，红黑树，堆，Trie树，B树，B+树...
红黑树（Red–black tree）是应用很广泛的一种平衡树，是面试官的装X利器。我们来看一下它保证平衡性的一些特性： 节点是红色或黑色。 根是黑色。 所有叶子都是黑色（叶子是NIL节点）。 这些约束确保了红黑树的关键特性：从根到叶子的最长路径不多于最短路径的两倍长(根据性质4和性质5)。从而整棵树的高度比较稳定，相应的增、删、改、查操作的效率较高较稳定，而不同于普通的二叉查找树。 堆 堆是一种特殊的数据结构，它满足两个特性： 堆是一个完全二叉树； 堆中每一个节点的排序值都必须大于等于（或小于等于）其左右子节点的排序值。 这里解释以下完全二叉树。 且利用了 数组和自身特性 增删改查的时间复杂度较低。 应用场景： 1.堆排序 2.TopK,求中位数，求 3.合并多个有序小文件或集合 4.优先队列，如定时任务的存储等... 3.命令自动补全，如zsh. 4.网址浏览历史记录。 5.手机号码簿查询... B树、B+树、LSM Tree是数据库中经常出现的数据结构。
5.1K30发布于 2020-07-30 - 来自专栏宇宙之_一粟
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 - 来自专栏leetcode_solutions
B树与B+树的区别
B+树的叶子节点由一条链相连，而B树的叶子节点各自独立。 使用B+树的好处 由于B+树的内部节点只存放键，不存放值，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。 这种特性使得B树在特定数据重复多次查询的场景中更加高效。 针对以上两个问题，B+树诞生了，B+树相比B树，本质上是一样的，区别就在与B+树的所有根节点都不带有任何数据信息，只有索引信息，所有数据信息全部存储在叶子节点里，这样，整个树的每个节点所占的内存空间就变小了 不仅如此，B+树还有一个相应的优质特性，就是B+树的查询效率是非常稳定的，因为所有信息都存储在了叶子节点里面，从根节点到所有叶子节点的路径是相同的。 B+树 （3) B+树的查询效率更加稳定 由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。
5K41发布于 2019-03-14 - 来自专栏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+树怎么作为？ ---- 代码实现 先占个位置，这几天是没办法了，有更重要的事情安排上了。忙完这两周，十月说什么也要安排上。
53420发布于 2021-10-09 - 来自专栏java达人
LSM树 与B+树比较
那么，为了使读取性能尽可能高，磁盘中的数据必须是有序的。这就是B+树的原理，但是写起来就很糟糕，因为会产生大量的随机IO，磁盘寻道速度跟不上。 关于b树 B+树最大的性能问题是会产生大量的随机io。 比如insert key跨度很大，7 -> 1000 -> 3 -> 2000... 新插入的数据存储在磁盘上，会产生大量的随机写IO。 例如，Oracle 的常用索引使用 B+ 树。 下面是一个B+树的例子 根节点和分支节点很简单，记录每个叶子节点的最小值，用指针指向叶子节点。 关于lsm树 LSM 树本质上是读写之间的平衡。与B+树相比，它牺牲了部分读取性能来提高写入性能。 以上就是LSM树最本质的原理，有了原理，再看具体的技术就很简单了： 关于lsm内存结构，可以是B+树，还可以为跳跃表（skip-list）或是一个有序字符串表（SSTables）。
1.3K20编辑于 2022-05-16 - 来自专栏JMCui
MySQL 的B+树索引.
一、B+树索引概述 索引是应用程序设计和开发的一个重要方面。若索引太多，应用程序的性能可能会受到影响（需维护索引的结构和数据）；而索引太少，对查询性能又会产生影响。 B+ 树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树，B+ 树中的 B 不是代表二叉（binary），而是代表平衡（balance）。 B+ 树索引的本质就是 B+ 树在数据库中的实现，但是 B+ 索引在数据库中有一个特点是高扇出性（数据库分区），因此在数据库中，B+ 树的高度一般都在 2-4 层，这也就是说查找某一键值的行记录时最多只需要 数据库中的 B+ 树索引可以分为 聚集索引和辅助索引。 B+ 树索引并不能找到一个给定键值的具体行。B+ 树索引能找到的只是被查找数据行所在的页。 这是由当前传统机械硬盘的特性所决定的，即利用顺序读来替换随机读的查找。可以使用关键字 FORCE INDEX 来强制使用某个索引。
1.2K20发布于 2020-08-14 - 来自专栏花落的技术专栏
红黑树、B树、B+树
现在假设搜索的结果是最左边的叶子节点 16，因为磁盘预读的特性，加上一个页能存储 5 个节点，第一次 I/O ： 第一次I/O 如上，第一次 I/O 就读取了 5 个节点，不仅把根节点读取进内存了，还把节点 B/B+树 B 树即：多路平衡查找树； B 树的巧妙之处在于： 将一个节点的大小设置为一页的大小； 一个节点可以存放多个关键字（多叉树）； 自平衡； 这 3 点结合起来就可以做到： 一个节点大小为一页， B/B+树的索引数量 B 树的节点中存储：指针、关键字(主键)、数据 B+ 树的非叶子节点：指针、关键字 B+树的叶子节点：指针(链表)、关键字、数据 注意，这里不是绝对的，比如有的 B+ 树中叶子节点存储的不是数据 而且上述是假设数据为 1KB，如果数据没那么大，高度为 3 的 B 树能存储更多的数据，但是如果用在大型数据库索引上还是不够。 B+ 树： B+树 如上图，B+树的核心在于非叶子节点不存储数据。 高度为 3 的 B+ 树进行两次 I/O 就可以索引千万级别的数据,高度为 4 的 B+ 树，进行 3 次 I/O 就能索引十亿级别的数据量，这个效果还是很好的。
1.2K40发布于 2021-11-25 - 来自专栏乐行僧的博客
B-树，B+树，B*树
1.减少磁盘的IO 2.更快的搜索算法 操作系统中， 管理内存是按照页page 4K 管理的 管理磁盘是按照block 16K 现在有n = 1000w个索引需要从磁盘中进行读取和搜索？ avl树和m为300的B-树？ avl树的高度：log2n = 24层 最差的情况一个节点只存储一个索引？ 最差需要24次磁盘IO B-树高度：log(300)n = 3 层 最多花费3次磁盘IO B+树 B+树是B-树的一种变形 非叶子结点只存储索引，不存储数据 B+树的叶子结点包含全部的关键字信息 ，而B-树的数据分散在各个结点当中。 B+树存放的索引项相对于B-树能够存储的更多。 B*树 B*树是B+树的变体，在B+树的非根和叶子结点在增加指向兄弟结点的指针 B*提高了结点的利用率。
1.4K30编辑于 2022-02-25 - 来自专栏我的技术专刊
红黑树、B树、B+树
现在假设搜索的结果是最左边的叶子节点 16，因为磁盘预读的特性，加上一个页能存储 5 个节点，第一次 I/O ： 第一次I/O 如上，第一次 I/O 就读取了 5 个节点，不仅把根节点读取进内存了，还把节点 B/B+树 B 树即：多路平衡查找树； B 树的巧妙之处在于： 将一个节点的大小设置为一页的大小； 一个节点可以存放多个关键字（多叉树）； 自平衡； 这 3 点结合起来就可以做到： 一个节点大小为一页， B/B+树的索引数量 B 树的节点中存储：指针、关键字(主键)、数据 B+ 树的非叶子节点：指针、关键字 B+树的叶子节点：指针(链表)、关键字、数据 注意，这里不是绝对的，比如有的 B+ 树中叶子节点存储的不是数据 而且上述是假设数据为 1KB，如果数据没那么大，高度为 3 的 B 树能存储更多的数据，但是如果用在大型数据库索引上还是不够。 B+ 树： B+树 如上图，B+树的核心在于非叶子节点不存储数据。 高度为 3 的 B+ 树进行两次 I/O 就可以索引千万级别的数据,高度为 4 的 B+ 树，进行 3 次 I/O 就能索引十亿级别的数据量，这个效果还是很好的。
95700编辑于 2021-12-05 - 来自专栏Java架构师必看
B树、B+树、B*树——简单介绍
如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树； 【2】2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。如下图就是一个2-3树； ? 【3】文件系统及数据库系统的设计者利用磁盘预读（预先读取）原理，将一个节点的大小设置为页<page:数据读取的最小单位>的大小（通常为4k），这样每个节点只需要一次 IO就能载入内存；B树(B+树)广泛应用于文件存储系统及数据库文件系统中 2-3 树基本介绍：最简单的 B树结构，具有如下特点： ■ 2-3 树的所有叶子节点都在同一层（只要是B树都满足这一点）； ■ 有两个子节点的叫二节点，二节点要么没有子节点，要么有两个子节点 三、B树、B+树、B*树 ---- 【1】B树介绍：前面介绍的2-3、2-3-4树就是 B树，在 MySql 中经常听说某种索引是基于 B树、B+树的，如下图： ? 【2】B+树介绍：B+ 树是B树的变体，也是一种多路搜索树，如下图： ? 【3】B* 树介绍：B* 树是B+树的变体，在B+树的非根和非叶子节点增加了指向兄弟的指针，如下图： ?
1.5K20发布于 2021-04-30 B树和B+树区别
具体区别1、叶子节点B树不存指针，B+树存双向指针，方便范围查找2、B树非叶子节点也存储数据，B+树不存储数据3、B树不会有冗余索引，是唯一的，B+树会有冗余索引4、存放同样的数据，B树的层级比B+树要高 ，因为B+树有冗余索引，所以相同层级的叶子节点的数据就会更多，（可以有更多的分叉）索引：如果存在主键，主键索引就是聚集索引如果不存在主键，将使用第一个唯一（UNIQUE）索引作为聚集索引。 如果表没有主键，或没有合适的唯一索引，则InnoDB会自动生成一个rowid作为隐藏的聚集索引。
37810编辑于 2024-06-06- 来自专栏业余草
图解B+树的插入过程
B+ 树在现代数据库中很常见，如果我们了解它，在工作中可能对性能优化会有更好的帮助！ 最近我一直在思考 B+ 树的高度是由什么决定的。知道我了解了 B+ 树的插入过程，才有一种恍然大悟的感觉！ 网上的一些资料杂乱无章，不同的数据库可能还有对 B+ 树有不同的实现。但是万变不离其宗，B+ 树的定义，大致如下所示： ? 总结一下，B+ 树有下面 5 个重要的特点。 下面以一棵 5 阶 B+ 树的插入过程，5 阶 B+ 树的节点最少 2 个 key，最多 4 个 key。 1、当树为空树，插入 5。 ? 只有一个关键字，叫根节点或叶子节点都是一样的。 2、再次插入 3 个索引关键字，8，10，15。 ? 当前节点 key 存满了，如果再插入当前节点就要进行分裂。 3、再插入关键字 16。 ? 可以看到，这个 B+ 树，现在满足分裂条件了。 通常，一棵 MySQL 的 B+ 树，树高为 3 的话，大约能存上亿条。树的高度太高的话，查询效率会大打折扣！
7.7K20发布于 2019-07-11 - 来自专栏JavaEE
多叉树 & B树 & B+树 & B*树
2-3树 2-3树是最简单的B树，它有以下特点： 首先它也要满足排序树的特点，即左子节点都比父节点小，右子节点都比父节点大，如果3节点，那么中间那个元素要介于左节点和右节点之间，即6是介于4和11之间的 比如2-3树的阶就是3，2-3-4树的阶就是4； B树的搜索：从根节点开始，对节点内的元素进行二分查找，如果找到就结束，否则进入查找元素所属范围的子节点再进行二分查找，直到找到或者到达叶子节点； B树的所有节点都会存放数据 B+树： B+树是B树的变体，和B树的区别就是，B+树所有数据都存放在叶子节点。 B+树所有的数据都存放在叶子节点的链表中，且链表中的数据也是有序的； 非叶子节点中存放的是索引，而不是要操作的数据，每个非叶子节点都会存放叶子节点的索引，也叫稀疏索引； B+树要进行搜素时，从根节点开始 B+树一般用于文件系统； 6. B*树： B*树又是B+树的变体，就是在B+树的基础上，在非根非叶子节点之间增加了指向兄弟节点的指针。
1.9K20发布于 2020-12-22 - 来自专栏xingoo, 一个梦想做发明家的程序员
B树 B-树 B+树 B*树
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点； B-树的特性： B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在 非叶子结点命中），其性能也等价于在关键字全集做一次二分查找； B+的特性： 1.所有关键字都出现在叶子结点的链表中 4.更适合文件索引系统； B*树 是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针； ? B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）； B+树的分裂： 当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点 ；B+树总是到叶子结点才命中； B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；
2.2K71发布于 2018-01-17 - 来自专栏性能与架构
mysql B+树索引
上图就是一棵B+树，每个部分有3个主要概念：物理磁盘块、数据项(蓝色)、指针(红色) 如磁盘块1，包含数据项 17、35，包含指针 P1、P2、P3，P1指向小于17的磁盘块，P2指向在17和35之间的磁盘块 ，P3指向大于35的磁盘块 真实的数据存于叶子节点中，即 3、5、9、10、13、15、28、29、36、60、75、79、90、99 非叶子节点中并不存放真实数据项，只存放指引搜索方向的数据项，如 17、35 并不真实存在于数据表中 B+树查找过程 如果要查找数据项29 1. 在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，通过P2指向的磁盘地址，把磁盘块3由磁盘加载到内存，发生第二次IO 3. 29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块 内存中做二分查找找到29，结束查询 总计三次IO，即可找到目标数据项 3层的B+树可以表示上百万的数据，对查询性能的提高是巨大的
1.1K80发布于 2018-04-02 - 来自专栏社区的朋友们
理解 B+ 树算法
B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。 另外说明的一点，B+中的B并不是代表二叉(Binary),而是代表平衡(Balance)。 对于m阶B+树，m的值越大，固定高度的B+树存放的值就越多。 在B+树的索引中，用户可以得到页表（或者叫块）级别的位置信息；但如果要进行一次比如key1到key3的范围查询，则可能需要读取两个在磁盘上不连续甚至可能相隔很远的叶子节点页表；这种情况，通常在B+树的设计中会含有一组被称为 举个栗子：往下图的3阶B+树中依次插入关键字：10、21、68、65、85 首先查找10应插入的叶节点(最左下角的那一个),插入发现没有破坏B+树的性质,完毕。 而B+树内部结点只需要1个盘块。当需要把内部结点读入内存中的时候，B 树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转寻道的时间)。
3.1K00发布于 2017-10-20
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号