MySQL底层数据结构选用B+树的原因

       我们都知道MySQL底层数据结构是选用的B+树，那为什么不用红黑树，或者其他什么数据结构呢？

        红黑树是一种自平衡二叉查找树，Java8中的hashmap就用到红黑树来优化它的查询效率，可见，红黑树的查询效率还是比较高的，但是为什么MySQL的底层不用红黑树而用B+数呢？

        下图是红黑树依次插入1,2,3,4,5,6之后的情况：

 然后再在上面的红黑树中插入7：

       可以看到，尽管红黑树经过了自平衡，数据整体仍然偏向树的右侧，如果继续添加更多数据，添加的数据上百万、千万之后，树的层级将会非常高，查询时每多经过一层，就会多进行一次io，树的层级多了之后查找效率就会很慢。这个时候可能就会有人问了，那为什么不用平衡性更好的AVL树呢？

        AVL树在一次插入1,2,3,4,5,6,7之后是这样的：

         的确变顺眼了很多，树的层数也变少了，可AVL仍然没有解决根本问题，当数据量达到百万、千万之后，树的层数仍然会比较大，先不说AVL树维护平衡所需的代价，单论AVL树的层数就无法达到我们的要求。

        那么什么样的数据结构可以让数据量达到百万，千万，甚至更大的体量时，层数仍然很小呢？很显然，想要减少层数，就必须要让每层储存的数据数更多，二叉树不管平衡性再好也只能做到每个节点有两个分叉，每层的数据量从数据结构被限制住了，那么，我们就不能从二叉树中选。所以这个时候B树的优势就体现出来了，B树每个节点可以存储多个元素，每个元素之间可以都可以拥有一个分叉，下图是B树每个节点最多可以存储3个元素的情况：

         可以看到树的层级减小到两层，如果说每次每个节点最多可以存储的元素个数足够大，那么就算数据量达到上千万的量级，也可以将树的层级控制在一个可以接受的范围内。

        但B树还有一个问题，下图展示的是B树层级达到三层时的情况：

         如果现在我需要取出5-10号元素，当我通过层层查询，找到5号元素，然后发现其他元素不在这个节点，还需要通过局部中序遍历查询其他元素，找到7之后还需如此操作找到8,9,10，这又会增加io次数，所以也就有了B+树。

        B+树是对B树的优化，主要是从两个地方进行优化的：

        第一个优化是在每个叶子节点之间加上了一个双向指针，指向相邻节点，这样就解决了刚才的范围查询问题，范围查询如果跨了多个节点，就可以通过这个双向指针快速找到相邻节点，而不需要通过局部的中序遍历，从而减少了io次数。下图演示的是B+树：

       但如果要找的元素不在叶子节点上呢？别担心，B+树的另一个优化就是的叶子节点包含了这颗树的所有元素！B+树的非叶子节点不再保存元素的data数据或者指针了，只是作为冗余的索引构成完整的B+树来方便查询。可以看到上图的15号元素不仅仅存在于非叶子节点中，也存在于叶子节点中。这样的设计虽然带来了很多冗余的索引，但是却让范围查询时不再需要向上查找非叶子节点了，而且每一层可以保存的索引数量变多了，让数据库每次io可以查询到更多的索引元素，毕竟在正常情况下，数据占的空间比索引占的空间要大很多。（需要注意的是，InnoDB和MyISAM引擎虽然都是用的B+树，但InnoDB的聚簇索引和数据是保存在一起的，而MyISAM是将聚簇索引和相应数据的指针保存在一起的，索引和数据是分开的。MyISAM引擎下的B+树也只有叶子节点才保存数据的指针）

        由上面的分析我们可以知道，选用B+树作为MySQL的底层是为了减少io次数，那我们为什么不直接极端一点，使用hash来保存数据或者索引呢？其实MySQL确实支持hash类型的索引。

        但是hash索引一般都不用，主要是因为hash索引的储存的是hash码，储存的顺序与索引列的值大小无关，所以只有在进行精确查找时hash索引才能生效，范围查询时会进行全表扫描。同时，如果表中的数据量非常大的话，发生hash碰撞的次数会增多，单个查找的效率不一定比B+树高。

        简单总结一下，B+树相比其他树来说，每个节点可以存储更多元素，可以大大减少查询时需要的io次数，非叶子节点不存储数据或指针的设计可以提高每个节点存储元素的数量，叶子节点具有的双向指针可以提高范围查询的效率。

到此这篇关于MySQL底层数据结构选用B+树的原因的文章就介绍到这了,更多相关MySQL B+树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 为什么MySQL数据库索引选择使用B+树?

    为什么MySQL数据库索引选择使用B+树?

    在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出B树以及为什么MySQL数据库索引选择使用B+树! 学过数据结构的一般对最基础的树都有所认识,因此我们就从与我们主题更为相近的二叉查找树开始. 一.二叉查找树 (1)二叉树简介: 二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质: 1.任意节点左子树不为空,则左子树的值均小于根节点的值: 2.任意节点右子

  • MySQL用B+树作为索引结构有什么好处

    MySQL用B+树作为索引结构有什么好处

    前言 在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引).本文将从最普通的二叉查找树开始,逐步说明各种树解决的问题以及面临的新问题,从而说明MySQL为什么选择B+树作为索引结构. 一.二叉查找树(BST):不平衡 二叉查找树(BST,Binary Search Tree),也叫二叉排序树,在二叉树的基础上需要满足:任意节点的左子树上所有节点值不大于根节点的值,任意节点的右子树上所有节点值不小于根节点的值.如下是一颗BST: 当需要快速查

  • mysql 使用B+树索引有哪些优势

    mysql 使用B+树索引有哪些优势

    搞懂这个问题之前,我们首先来看一下MySQL表的存储结构,再分别对比二叉树.多叉树.B树和B+树的区别就都懂了. MySQL的存储结构 表存储结构 单位:表>段>区>页>行 在数据库中, 不论读一行,还是读多行,都是将这些行所在的页进行加载.也就是说存储空间的基本单位是页. 一个页就是一棵树B+树的节点,数据库I/O操作的最小单位是页,与数据库相关的内容都会存储在页的结构里. B+树索引结构 在一棵B+树中,每个节点为都是一个页,每次新建节点的时候,就会申请一个页空间 同一层的节点

  • MySQL的索引系统采用B+树的原因解析

    MySQL的索引系统采用B+树的原因解析

    目录 1.什么是索引? 2.为什么需要索引? 3.如何设计索引系统? 4.MYSQL索引系统是什么呢? 5.哈希表 6.树 6.1 二叉树 6.2 二分查找树(Binary Search Tree ,BST) 6.3 平衡二叉树(Balanced Binary Tree, AVL树) 6.4 红黑树 6.5 B树 6.6 B+树 总结 1.什么是索引? 索引是为了加速对表中数据行的检索而创建的一种分散的存储结构.(就好像我们小时候用的字典,有了字典查到对应的字就会变快) 2.为什么需要索引? 首

  • MySQL底层数据结构选用B+树的原因

    MySQL底层数据结构选用B+树的原因

           我们都知道MySQL底层数据结构是选用的B+树,那为什么不用红黑树,或者其他什么数据结构呢?         红黑树是一种自平衡二叉查找树,Java8中的hashmap就用到红黑树来优化它的查询效率,可见,红黑树的查询效率还是比较高的,但是为什么MySQL的底层不用红黑树而用B+数呢?         下图是红黑树依次插入1,2,3,4,5,6之后的情况:  然后再在上面的红黑树中插入7:        可以看到,尽管红黑树经过了自平衡,数据整体仍然偏向树的右侧,如果继续添加更多数

  • MySQL索引底层数据结构详情

    MySQL索引底层数据结构详情

    目录 一.索引类型 1.B+树 2.MyISAM和InnoDB的B+树索引实现方式的区别(聚簇索引和非聚簇索引)? 3.非聚簇索引 4.聚簇索引的优缺点 5.哈希索引 6.自适应哈希索引 一.索引类型 1.B+树 为什么是B+树而不是B树? 首先看看B树和B+树在结构上的区别 B树结构: B+树: 可以看到: B树在每个节点上都有卫星数据(数据表中的一行数据),而B+树只在叶子节点上有卫星数据.这意味着相同大小的磁盘扇区,B+树可以存储的叶子节点更多,磁盘IO次数更少:同样也意味着B+树的查找效

  • 浅析MySQL索引结构采用B+树的问题

    浅析MySQL索引结构采用B+树的问题

    目录 1.B树和B+树 2.原因分析 3.总结 一位6年经验的小伙伴去字节面试的时候被问到这样一个问题,为什么MySQL索引结构要采用B+树?这位小伙伴从来就没有思考过这个问题.只因为现在都这么卷,后面还特意查了很多资料,他也希望听听我的见解. 另外,我花了1个多星期把往期的面试题解析配套文档准备好了,一共有10万字,想获取的小伙伴可以在我的煮叶简介中找到. 1.B树和B+树 一般来说,数据库的存储引擎都是采用B树或者B+树来实现索引的存储.首先来看B树,如图所示. B树是一种多路平衡树,用这种

  • MySQL limit分页大偏移量慢的原因及优化方案

    在 MySQL 中通常我们使用 limit 来完成页面上的分页功能,但是当数据量达到一个很大的值之后,越往后翻页,接口的响应速度就越慢. 本文主要讨论 limit 分页大偏移量慢的原因及优化方案,为了模拟这种情况,下面首先介绍表结构和执行的 SQL. 场景模拟 建表语句 user 表的结构比较简单,id.sex 和 name,为了让 SQL 的执行时间变化更加明显,这里有9个姓名列. CREATE TABLE `user` ( `id` int(11) NOT NULL AUTO_INCREME

  • Redis底层数据结构详解

    Redis底层数据结构详解

    Redis作为Key-Value存储系统,数据结构如下: Redis没有表的概念,Redis实例所对应的db以编号区分,db本身就是key的命名空间. 比如:user:1000作为key值,表示在user这个命名空间下id为1000的元素,类似于user表的id=1000的行. RedisDB结构 Redis中存在"数据库"的概念,该结构由redis.h中的redisDb定义. 当redis 服务器初始化时,会预先分配 16 个数据库 所有数据库保存到结构 redisServer 的一

  • 深入解析MySQL索引数据结构

    深入解析MySQL索引数据结构

    目录 概述 索引数据结构 二叉树 红黑树 B-Tree B+Tree Hash 索引 InnoDB 索引实现(聚集) 索引文件和数据文件是分离的(非聚集) 聚集索引和非聚集索引 联合/复合索引 参考资料 总结 概述 索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息. 索引数据结构 二叉树 二叉树(binary tree)是指树中节点的度不大于 2 的有序树,它是一种最简单且最重要的树.二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不

  • mysql索引失效的常见九种原因图文详解

    mysql索引失效的常见九种原因图文详解

    目录 前言: 1.最佳左前缀法则 3.计算.函数.类型转换(自动或手动)导致索引失效 4.范围条件右边的列索引失效 5.不等于(!= 或者<>)导致索引失效 6.is null可以使用索引,is not null无法使用索引 7.like以通配符%开头索引失效 8.OR 前后只要存在非索引的列,都会导致索引失效 9.数据库和表的字符集统一使用utf8mb4 总结 前言: MySQL中提高性能的一个最有效的方式是对数据表设计合理的索引.索引提供了高效访问数据的方法,并且加快查询的速度, 因此索引

  • 一步步带你学习设计MySQL索引数据结构

    目录 前言 索引介绍 索引设计目标 索引设计迭代 迭代一 迭代二 迭代三 迭代四 迭代小结 索引结构总结 聚簇索引 非聚簇索引 联合索引 索引优点和缺点 优点 缺点 总结 前言 MySQL的索引是一个非常重要的知识点,也基本上是面试必考的一个技术点,所以非常重要.那你了解MySQL索引的数据结构是怎么样的吗?为什么要采用这样的数据结构? 现在化身为MySQL的架构师,一步步迭代设计出MySQL的索引结构,保证你再也忘记不了索引的结构了,轻松通过面试. 索引介绍 MySQL表中存储的数据量非常大,

  • C语言数据结构之中缀树转后缀树的实例

    C语言数据结构之中缀树转后缀树的实例 对于一个中缀表达式 a+b*c*(d-e/f) 转换成后缀是这样的形式 abc*def/-+ 后缀表达式是相当有用处的,转换成后缀表达式后求值会简单很多.那么该如何转换呢? 网上关于这方面的资料一搜一大把,每本数据结构的书中都会提及这个算法,在这个算法中,用到 栈 这个数据结构. 1,关键是比较运算符的优先级,谁的优先级高,谁就出现在前面上面的表达式中,有括号的时候括号优先级最高,*/次之,+-最后. 在上面的表达式中+的优先级不如*的高,因此,在后缀表达式

随机推荐