成都网站设计龙兵科技,wordpress404页面更爱,网页设计与网站开发试卷,自定义wordpress后台本文先介绍数据结构中树的演化过程#xff0c;之后介绍为什么MySQL数据库选择了B树作为索引结构。 文章目录 树的演化为什么其他树结构不行#xff1f;为什么不使用二叉查找树#xff08;BST#xff09;#xff1f;为什么不使用平衡二叉树#xff08;AVL树#xff09;之后介绍为什么MySQL数据库选择了B树作为索引结构。 文章目录 树的演化为什么其他树结构不行为什么不使用二叉查找树BST为什么不使用平衡二叉树AVL树为什么不使用B树 为什么选择 B 树1. B 树节点结构2. 优点举例 QAHash比B树更快为什么Mysql用B树来存储索引呢增加树的路数可以降低树的高度那么无限增加树的路数是不是可以有最优的查找效率 树的演化 树 非线性结构每个节点有唯一的一个父结点和多个子结点子树为一对多的关系。 二叉树 每个结点最多有两颗子树并且子树有左右之分不能颠倒。 满二叉树 每一层的结点个数都达到了当层能达到的最大结点数。 完全二叉树 除了最下面一层之外其余层的结点个数都达到了当层能达到的最大结点数且最下面一层只从左至右连续存在若干结点右边的结点全部不存在。 二叉查找树 (BST) 又称为二叉排序树、二叉搜索树。定义 要么二叉査找树是一棵空树。要么二叉查找树由根结点、左子树、右子树组成其中左子树和右子树都是二叉查找树其中 左子树的所有结点值小于或等于根节点值右子树的所有结点值大于根节点值。 平衡二叉树 (AVL 树) 特殊的二叉查找树左右子树都是平衡二叉树且左右子树高度之差不超过 1。 B 树 又名平衡多路查找树。每个节点包含多个数据及指针域查找路径有多个分支。B-树就是 B 树别讲什么B减树‘-’是分隔符。 B 树 在 B 树基础上发展而来的平衡多路查找树非叶子节点只存储键值和指针所有数据存储在叶子节点并通过链表连接。 优化主要体现在以下几个方面 非叶子节点不存储数据更适合磁盘存储和 I/O 优化 B 树所有节点都存储键值和数据。B 树非叶子节点只存储键值和指针不存储实际数据使得内部非叶子节点更小单个磁盘块可容纳更多键值减少树的高度和磁盘 I/O 次数降低树的高度。 叶子节点存储所有数据更便于顺序遍历查找效率稳定 B 树数据分散在各个节点遍历需要中序遍历整棵树。 查询可能在任何节点结束查询效率不稳定。B 树所有数据存储在叶子节点并通过链表连接范围查询、排序查询更高效可以快速顺序遍历数据无需回溯所有查询最终都在叶子节点结束查找效率稳定。
为什么其他树结构不行
磁盘读写的特性
数据库的索引及数据存储在磁盘中而不是内存中磁盘 I/O 的速度远慢于内存。从磁盘读取数据时按照磁盘块页读取每次读取的最小单位是一个磁盘块。若能将更多数据放入一个磁盘块中一次读取操作可以获取更多数据从而减少 I/O 次数提高查询效率。
为什么不使用二叉查找树BST
可能出现链表形态二叉查找树在数据不平衡时可能退化成一条链表类似于全表扫描查找时无法发挥二叉排序树的优势。高度过高树的高度过高时查找效率变得不稳定查询需要遍历较多的节点导致性能下降。
为什么不使用平衡二叉树AVL树
平衡二叉树通过自平衡解决了BST高度过高查找效率不稳定的问题。但是
节点存储限制平衡二叉树每个节点只能存储一个键值和数据对于海量数据节点数量会非常多树的高度依然可能较高。效率降低对于大量数据的存储和查找效率依然不理想因为节点存储量有限高度无法有效缩减。
为什么不使用B树
B树每个节点有更多子节点减少了树的高度从而提高了IO性能。解决了平衡二叉树只能存储一个键值和数据的问题。但是
遍历效率低尽管B树提高了IO性能但在查找数据时仍然需要遍历整个树导致遍历效率低不同的点查询效率不一样即查询效率不稳定。
为什么选择 B 树 二叉查找树可能退化为链表查找效率不稳定。平衡二叉树虽然能保证平衡但对于海量数据节点数仍多高度过高。B树提高了IO性能解决了平衡二叉树的问题但遍历效率不足特别是对于大范围查询。
引入B树为了进一步提高遍历效率B树在B树的基础上做了优化
1. B 树节点结构
非叶子节点仅存储键值不存储数据节点更紧凑。数据只存储在叶子节点叶子节点通过双向链表串联形成线性表。查询时只需要扫描叶子节点从而大幅提高了范围查询和排序查询的效率。数据库页的大小固定如 InnoDB 默认 16KB更高阶数的树更矮更胖减少了磁盘 I/O 次数。
2. 优点 磁盘读写代价更低 内部节点不存储数据节点更小单个磁盘块可容纳更多键值。减少树的高度相同数据量下 I/O 次数更少。 查询效率更加稳定 查询路径固定从根节点到叶子节点的路径长度一致每次查询效率相同。 更便于遍历 数据全部存储在叶子节点顺序遍历时只需扫描叶子节点即可。非叶子节点均为索引便于范围查询和排序。 更适合范围查询 叶子节点通过链表连接直接支持高效的范围查询和排序操作。在数据库中基于范围的查询非常频繁而 B 树不支持或效率较低。 举例
磁盘页大小默认是 16 KB也就是16,384 字节1 KB 1024 字节。 假设条件 2. 每个键值的大小假设每个键值的大小是 16 字节。 3. 每个节点存储的键值数量每个磁盘页可以存储 1024 个键值。
如果一个节点可以存储 1000 个键值时没有超过1024 个键值3 层的 B 树可以存储约 10 亿条数据。根节点常驻内存那么查找 10 亿条数据时只需 2 次磁盘 I/O。 QA
Hash比B树更快为什么Mysql用B树来存储索引呢
首先在功能上
B树可以进行BETWEEN范围查询Hash索引不能。B树支持order by排序Hash索引不支持。B树使用like 进行模糊查询的时候like后面比如%开头的话可以起到优化的作用Hash索引根本无法进行模糊查询。B树支持 InnoDB、MyISAM 和 MemoryHash索引仅支持Memory默认情况B树支持联合索引的最左侧原则Hash索引不支持。Hash索引在等值查询上比B树效率更高。
从设计上来看
从内存角度上说数据库中的索引一般时在磁盘上数据量大的情况可能无法一次性装入内存B树的设计可以允许数据分批加载。从业务场景上说等值查询那确实是hash更快但是数据库中经常会进行排序和范围查询B树叶子节点通过双向链表串联形成线性表它的查询效率比hash就快很多了hash还需要解决冲突。
增加树的路数可以降低树的高度那么无限增加树的路数是不是可以有最优的查找效率
答这样会形成一个有序数组文件系统和数据库的索引都是存在硬盘上的并且如果数据量大的话不一定能一次性加载到内存中。有序数组没法一次性加载进内存这时候B树的多路存储威力就出来了可以每次加载B树的一个结点然后一步步往下找。
