网站跳转怎么做,做网站建议,建立个人网站怎么赚钱,怎么看网站做没做备案文章目录 B树与B树的基本概念B树#xff08;Balanced Tree#xff09;B树#xff08;B-Plus Tree#xff09;对比 为什么MySQL选择B树1. **磁盘I/O效率**2. **更稳定的查询性能**3. **更高的空间利用率**4. **并发控制** 其他树结构的比较参考 索引是一种
数据结构#x… 文章目录 B树与B树的基本概念B树Balanced TreeB树B-Plus Tree对比 为什么MySQL选择B树1. **磁盘I/O效率**2. **更稳定的查询性能**3. **更高的空间利用率**4. **并发控制** 其他树结构的比较参考 索引是一种
数据结构用于帮助我们在大量数据中快速定位到我们想要查找的数据。MySQL索引有三类B树索引、Hash索引、全文索引 在数据库系统中索引是提高数据检索效率的关键工具。而在MySQL中B树索引是最常用的一种索引结构。理解为什么MySQL选择使用B树而不是B树或其他树结构首先需要深入了解B树和B树的特性及其在数据库检索中的表现。
B树与B树的基本概念
B树Balanced Tree
B树是一种自平衡的多叉树数据结构其中每个节点可以包含多个子节点和键。B树的每个节点都包含键和子节点指针叶子节点不需要保持在同一层。
B树的特性包括
每个节点包含多个键每个节点至少包含 ⌈m/2⌉−1个键至多包含 m−1 个键m 为B树的阶数。所有叶子节点在相同深度树的所有叶子节点处于同一深度。平衡性插入和删除操作保持树的平衡。
B树B-Plus Tree
B树是B树的一种变体具有以下特点
叶子节点链表所有叶子节点通过链表相连形成一个有序链表。非叶子节点只存储键非叶子节点不存储数据只存储键和子节点指针数据仅存储在叶子节点中。更高的节点分支因子因为非叶子节点只存储键B树相对于同阶的B树可以存储更多的键从而减少树的高度。
对比
特性B树B树节点存储键和数据内部节点存储键叶子节点存储数据键的数量⌈m/2⌉−1到 m−1⌈m/2⌉−1到 m−1子节点指针数量⌈m/2⌉ 到 m⌈m/2⌉ 到 m数据存储位置内部节点和叶子节点仅在叶子节点叶子节点链表不存在存在叶子节点通过链表连接查询效率O(logmN)从根节点到叶子节点O(logmN)从根节点到叶子节点插入/删除操作相对复杂需要调整节点相对复杂需要调整叶子节点链表和节点范围查询效率较差需要遍历多个节点优秀叶子节点通过链表有序连接顺序访问较差需要中序遍历树优秀通过链表遍历叶子节点空间利用率较高较高叶子节点存储更多数据适用场景频繁插入、删除操作高效范围查询、顺序访问、数据库索引
B树
适用于需要频繁插入和删除操作的场景。数据既存储在内部节点也存储在叶子节点。查询和更新操作效率较高但范围查询和顺序访问效率较低。
B树
适用于需要高效范围查询和顺序访问的场景。数据仅存储在叶子节点内部节点只存储键。叶子节点通过链表连接提高了范围查询和顺序访问的效率。
为什么MySQL选择B树
1. 磁盘I/O效率
数据库检索的效率很大程度上取决于磁盘I/O操作的效率。B树的结构有利于减少磁盘I/O操作
叶子节点链表B树的所有叶子节点通过链表相连支持顺序访问。当进行范围查询时只需在链表中遍历叶子节点即可大大提高了范围查询的效率。更高的节点分支因子由于非叶子节点只存储键B树可以在同样大小的节点中存储更多的键和子节点指针从而减少树的高度。更少的高度意味着在检索时需要更少的磁盘I/O操作。
2. 更稳定的查询性能
B树的查询性能更加稳定尤其是在范围查询和排序操作中表现突出
范围查询B树的叶子节点通过链表相连进行范围查询时只需遍历链表性能较为稳定。排序B树的叶子节点本身是有序的支持高效的排序操作。
3. 更高的空间利用率
B树的空间利用率更高因为它将数据仅存储在叶子节点中而非叶子节点只存储键和指针。相比之下B树的每个节点都存储数据和指针导致空间利用率较低。
4. 并发控制
B树的结构有助于提高并发控制能力
分裂和合并操作在插入和删除操作时B树的分裂和合并操作相对简单且对树的结构影响较小这有助于提高并发操作的性能和稳定性。
与 B 树相比B树具有以下优点
更矮胖的树: B树的非叶子结点不存储数据因此可以存储更多的索引从而使树更加矮胖。这使得查询数据时需要访问的树的层数更少从而提高查询效率。更快的范围查询: B树的叶子结点按关键字顺序存储并且相邻的叶子结点之间有指针相连因此可以很有效地支持范围查询。
B树与B树比较
B树层级更少查找更快B树查询速度稳定由于B树所有数据都存储在叶子节点所以查询任意数据的次数都是树的高度hB树有利于范围查找B树全节点遍历更快所有叶子节点构成链表全节点扫描只需遍历这个链表即可B树优点如果在B树中查找的数据离根节点近由于B树节点中保存有数据那么这时查询速度比B树快。
其他树结构的比较
虽然B树在数据库索引中表现优异但了解其他树结构的优缺点也有助于全面理解数据库索引的选择
AVL树AVL树是一种高度平衡的二叉搜索树每次插入和删除操作都会导致旋转以保持平衡。虽然AVL树的查找效率高但由于频繁的旋转操作其插入和删除效率较低不适合频繁更新的数据库环境。红黑树红黑树是一种自平衡的二叉搜索树通过颜色标记节点并进行旋转操作来保持平衡。红黑树的插入和删除效率高于AVL树但由于其二叉结构相对于多叉树的B树磁盘I/O效率较低。
各种树解决的问题以及面临的新问题 二叉查找树(BST)解决了排序的基本问题但是由于无法保证平衡可能退化为链表 平衡二叉树(AVL)通过旋转解决了平衡的问题但是旋转操作效率太低 红黑树通过舍弃严格的平衡和引入红黑节点解决了AVL旋转效率过低的问题但是在磁盘等场景下树仍然太高IO次数太多 B树通过将二叉树改为多路平衡查找树解决了树过高的问题 B树在B树的基础上将非叶节点改造为不存储数据的纯索引节点进一步降低了树的高度此外将叶节点使用指针连接成链表范围查询更加高效。
MySQL选择B树作为索引结构是基于其在磁盘I/O效率、查询性能、空间利用率和并发控制等方面的优势。B树通过将数据存储在叶子节点并使用链表连接叶子节点实现了高效的范围查询和排序操作同时减少了磁盘I/O操作的次数提供了稳定的查询性能。这些特点使得B树成为MySQL数据库索引的首选结构。
参考
知乎 - MySQL 为什么使用 B 树来作索引Github - B树和B树详解
