MySQL中B+ Tree的原理解析
发布时间：2022-01-21 13:29:24 所属栏目：MySql教程 来源：互联网
导读：这篇文章主要介绍MySQL中B+ Tree的原理分析，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！ 前言 由于MySQL的索引中最重要的数据结构就是B+树，所以前面我们先大概讲讲B+树的原理 B+ Tree 原理 1. 数据结构 B Tree 指的是 Balanc
|
这篇文章主要介绍MySQL中B+ Tree的原理分析，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！ 前言 由于MySQL的索引中最重要的数据结构就是B+树，所以前面我们先大概讲讲B+树的原理 B+ Tree 原理 1. 数据结构 B Tree 指的是 Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。 B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高区间查询的性能。 2. 操作 进行查找操作时，首先在根节点进行二分查找，找到一个 key 所在的指针，然后递归地在指针所指向的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的 data。 插入删除操作会破坏平衡树的平衡性，因此在插入删除操作之后，需要对树进行一个分裂、合并、旋转等操作来维护平衡性。 3. 与红黑树的比较 红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，主要有以下两个原因： （一）更少的查找次数 平衡树查找操作的时间复杂度等于树高 h，而树高大致为 O(h)=O(logdN)，其中 d 为每个节点的出度。 红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多，查找的次数也就更多。 （二）利用磁盘预读特性 为了减少磁盘 I/O，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的旋转时间，速度会非常快。 操作系统一般将内存和磁盘分割成固态大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性，相邻的节点也能够被预先载入。 （编辑：应用网_丽江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330468号