欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Mysql 为什么要选择 B+Tree

程序员文章站 2023-11-08 15:36:22
算法对比 二叉树 当我查找 8 的时候需要走五步 红黑树 当我查询8的时候需要四次 相对于二叉树有了一些优化 没有无限延伸.红黑树的深度会很深(深度不可控制) hash 数据量大的话 查询很快(不能范围查找) BTree 查询只需要查两步就可以找到,缺点携带(data)扩大横向减少纵向深度 ps:j ......

算法对比

二叉树

Mysql 为什么要选择 B+Tree

当我查找 8 的时候需要走五步

Mysql 为什么要选择 B+Tree

红黑树

Mysql 为什么要选择 B+Tree

当我查询8的时候需要四次 相对于二叉树有了一些优化 没有无限延伸.红黑树的深度会很深(深度不可控制)

Mysql 为什么要选择 B+Tree

hash

数据量大的话

Mysql 为什么要选择 B+Tree

查询很快(不能范围查找)

btree

Mysql 为什么要选择 B+Tree

查询只需要查两步就可以找到,缺点携带(data)扩大横向减少纵向深度
ps:java拿取数据一般是这样的:java程序-->cpu--->内存---->硬盘,而内存与硬盘的交互是有大小限制的,是一页数据4k左右,所以不能把所有数据都放在一个节点来获取,一般来说节点会尽量预存4k容量。

Mysql 为什么要选择 B+Tree

b+tree

Mysql 为什么要选择 B+Tree

btree 变种b+tree
ps:data不放在非叶子节点来增加度(小节点),一般会一百个以上使得深度是3~5,从而减少查询次数。并且,叶子节点之间会有指针,数据又是递增的,这使得我们范围查找可以通过指针连接查找,而不再从上面节点往下一个个找。既减少了查询次数,又提供了范围查询.
所以mysql采用的b+tree算法

Mysql 为什么要选择 B+Tree