---
date: 2021-09-13
---

# B 树是什么

[B 树 - 维基百科](https://zh.wikipedia.org/wiki/B%E6%A0%91)

B 树（英语：B-tree）是一种 ` 自平衡 ` 的树，能够保持 ` 数据有序 `。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B 树，概括来说是一个 ` 一般化的二叉查找树 `（binary search tree）一个节点可以拥有 `2 个以上的子节点 `。与自平衡二叉查找树不同，B 树适用于读写相对大的数据块的存储系统，例如磁盘。B 树减少定位记录时所经历的中间过程，从而加快存取速度。B 树这种数据结构可以用来描述 ` 外部存储 `。这种数据结构常被应用在数据库和文件系统的实现上。

![](http://yano.oss-cn-beijing.aliyuncs.com/blog/20210913174937.png?x-oss-process=style/yano)

![](http://yano.oss-cn-beijing.aliyuncs.com/blog/20210913174958.png?x-oss-process=style/yano)

# B + 树是什么

[B + 树 - 维基百科](https://zh.wikipedia.org/wiki/B%2B%E6%A0%91)

B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。

B+ 树在 ` 节点访问时间远远超过节点内部访问时间 ` 的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。

B+ 背后的想法是内部节点可以有在预定范围内的 ` 可变量目的子节点 `。因此，B+ 树不需要像其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树（常简称为 2-3 树）中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。

![](http://yano.oss-cn-beijing.aliyuncs.com/blog/20210913175100.png?x-oss-process=style/yano)

# 为什么 B + 树比 B 树更适合磁盘存储？

- 查询的时间复杂度：
  - B 树：最好为 O(1)，最坏为 O(logn)。非叶子节点和叶子节点都存储数据。
  - B+ 树：固定为 O(logn)。仅在叶子节点存储数据，非叶子节点仅存储关键字。
- B + 树`叶子节点间用链表相互连接`，只要扫描叶子节点就可以完成一次`遍历操作`，B 树只能使用中序遍历。
- B + 树更适合磁盘，比 B 树少 I/O 读写次数。因为索引文件很大，且存在磁盘上，`B + 树的非叶子节点单页能存储更多的关键字 `，一次读入内存的关键字越多，磁盘的随机 I/O 读取次数就越少。
- B + 树查询效率更稳定，固定为 O(logn)。

# GitHub 项目

[Java 编程思想 - 最全思维导图 - GitHub 下载链接](https://github.com/LjyYano/Thinking_in_Java_MindMapping)，需要的小伙伴可以自取~

原创不易，希望大家转载时请先联系我，并标注原文链接。