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

前言

在MySQL中，无论是Innodb还是MyIsam，都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始，逐步说明各种树解决的问题以及面临的新问题，从而说明MySQL为什么选择B+树作为索引结构。

一、二叉查找树(BST)：不平衡

二叉查找树(BST，Binary Search Tree)，也叫二叉排序树，在二叉树的基础上需要满足：任意节点的左子树上所有节点值不大于根节点的值，任意节点的右子树上所有节点值不小于根节点的值。如下是一颗BST：

当需要快速查找时，将数据存储在BST是一种常见的选择，因为此时查询时间取决于树高，平均时间复杂度是O(lgn)。然而，BST可能长歪而变得不平衡，如下图所示，此时BST退化为链表，时间复杂度退化为O(n)。

为了解决这个问题，引入了平衡二叉树。

二、平衡二叉树(AVL)：旋转耗时

AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。

AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。

由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

三、红黑树：树太高

与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看，红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一，且节点颜色的划分需要满足特定的规则(具体规则略)。红黑树示例如下：

与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转。总的来说，红黑树的统计性能高于AVL。

因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树存储排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。

对于数据在内存中的情况（如上述的TreeMap和HashMap），红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树并不擅长，因为红黑树长得还是太高了。当数据在磁盘中时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会严重影响性能。

四、B树：为磁盘而生

B树也称B-树(其中不是减号)，是为磁盘等辅存设备设计的多路平衡查找树，与二叉树相比，树的每个非叶节点可以有多个子树。因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。

定义B树最重要的概念是阶数(Order)，对于一颗m阶B树，需要满足以下条件：

  • 每个节点最多包含 m 个子节点。
  • 如果根节点包含子节点，则至少包含 2 个子节点；除根节点外，每个非叶节点至少包含 m/2 个子节点。
  • 拥有 k 个子节点的非叶节点将包含 k - 1 条记录。
  • 所有叶节点都在同一层中。

可以看出，B树的定义，主要是对非叶结点的子节点数量和记录数量的限制。

下图是一个3阶B树的例子：

B树的优势除了树高小，还有对访问局部性原理的利用。所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。

B树在数据库中有一些应用，如mongodb的索引使用了B树结构。但是在很多数据库应用中，使用了是B树的变种B+树。

五、B+树

B+树也是多路平衡查找树，其与B树的区别主要在于：

  • B树中每个节点（包括叶节点和非叶节点）都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。在MySQL中，这里所说的真实数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。
  • B树中一条记录只会出现一次，不会重复出现，而B+树的键则可能重复重现——一定会在叶节点出现，也可能在非叶节点重复出现。
  • B+树的叶节点之间通过双向链表链接。
  • B树中的非叶节点，记录数比子节点个数少1；而B+树中记录数与子节点个数相同。

由此，B+树与B树相比，有以下优势：

  • **更少的IO次数：**B+树的非叶节点只包含键，而不包含真实数据，因此每个节点存储的记录个数比B数多很多（即阶m更大），因此B+树的高度更低，访问时所需要的IO次数更少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。
  • **更适于范围查询：**在B树中进行范围查询时，首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；而B+树的范围查询，只需要对链表进行遍历即可。
  • **更稳定的查询效率：**B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)，而B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。

B+树也存在劣势：由于键会重复出现，因此会占用更多的空间。但是与带来的性能优势相比，空间劣势往往可以接受，因此B+树的在数据库中的使用比B树更加广泛。

六、感受B+树的威力

前面说到，B树/B+树与红黑树等二叉树相比，最大的优势在于树高更小。实际上，对于Innodb的B+索引来说，树的高度一般在2-4层。下面来进行一些具体的估算。

树的高度是由阶数决定的，阶数越大树越矮；而阶数的大小又取决于每个节点可以存储多少条记录。Innodb中每个节点使用一个页(page)，页的大小为16KB，其中元数据只占大约128字节左右(包括文件管理头信息、页面头信息等等)，大多数空间都用来存储数据。

  • 对于非叶节点，记录只包含索引的键和指向下一层节点的指针。假设每个非叶节点页面存储1000条记录，则每条记录大约占用16字节；当索引是整型或较短的字符串时，这个假设是合理的。延伸一下，我们经常听到建议说索引列长度不应过大，原因就在这里：索引列太长，每个节点包含的记录数太少，会导致树太高，索引的效果会大打折扣，而且索引还会浪费更多的空间。
  • 对于叶节点，记录包含了索引的键和值(值可能是行的主键、一行完整数据等，具体见前文)，数据量更大。这里假设每个叶节点页面存储100条记录(实际上，当索引为聚簇索引时，这个数字可能不足100；当索引为辅助索引时，这个数字可能远大于100；可以根据实际情况进行估算)。

对于一颗3层B+树，第一层(根节点)有1个页面，可以存储1000条记录；第二层有1000个页面，可以存储1000 * 1000条记录；第三层(叶节点)有1000 * 1000个页面，每个页面可以存储100条记录，因此可以存储1000 * 1000 * 100条记录，即1亿条。而对于二叉树，存储1亿条记录则需要26层左右。

七、总结

最后，总结一下各种树解决的问题以及面临的新问题：

  1. 二叉查找树(BST)：解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表；
  2. 平衡二叉树(AVL)：通过旋转解决了平衡的问题，但是旋转操作效率太低；
  3. 红黑树：通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多
  4. B树：通过将二叉树改为多路平衡查找树，解决了树过高的问题；
  5. B+树：在B树的基础上，将非叶节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查询更加高效。

以上就是MySQL用B+树作为索引结构有什么好处的详细内容，更多关于MySQL B+树索引结构的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Mysql 索引结构直观图解介绍

    Mysql 索引结构直观图解介绍

    一.模拟创建原始数据 下图中,左边是自己方便说明,模拟的数据.引擎为mysiam~ 右边是用EXCEL把它们随机排列后的一个正常仿真数据表,把主键按照1-27再排列(不随机的话我在模拟数据时本来就是按顺序写的,再加索引看不大出这个索引排序的过程) 也就是说右边的数据,使我们要测试的原始数据,没建索引前是这样排序的,后边所有的数据都是以这个为依准进行的,这样更好看索引生成后的排序效果. 该表有4个字段(id,a,b,c),共21行数据 二.创建索引 a 如下图,当创建索引a以后,在该索引结构中,从

  • 获取 MySQL innodb B+tree 的高度的方法

    前言 MySQL 的 innodb 引擎之所以使用 B+tree 来存储索引,就是想尽量减少数据查询时磁盘 IO 次数.树的高度直接影响了查询的性能.一般树的高度在 3~4 层较为适宜.数据库分表的目的也是为了控制树的高度.那么如何获取树的高度呢?下面使用一个示例来说明如何获取树的高度. 示例数据准备 建表语句如下: CREATE TABLE `user` (   `id` int(11) NOT NULL AUTO_INCREMENT,   `name` varchar(100) CHARAC

  • MySql范围查找时索引不生效问题的原因分析

    MySql范围查找时索引不生效问题的原因分析

    1 问题描述 本文对建立好的复合索引进行排序,并取记录中非索引字段,发现索引不生效,例如,有如下表,DDL语句为: CREATE TABLE `employees` ( `emp_no` int(11) NOT NULL, `birth_date` date NOT NULL, `first_name` varchar(14) NOT NULL, `last_name` varchar(16) NOT NULL, `gender` enum('M','F') NOT NULL, `hire_da

  • MySQL如何基于Explain关键字优化索引功能

    explain显示了MySQL如何使用索引来处理select语句以及连接表.可以帮助选择更好的索引和写出更优化的查询语句.简单讲,它的作用就是分析查询性能. explain关键字的使用方法很简单,就是把它放在select查询语句的前面. mysql查看是否使用索引,简单的看type类型就可以.如果它是all,那说明这条查询语句遍历了所有的行,并没有使用到索引. 比如:explain select * from company_info where cname like '%小%' explain

  • Mysql索引常见问题汇总

    Q1:数据库有哪些索引?优缺点是什么? 1.B树索引:大多数数据库采用的索引(innoDB采用的是b+树).能够加快访问数据的速度,尤其是范围数据的查找非常快.缺点是只能从索引的最左列开始查找,也不能跳过索引中的列,如果查询中有某个列用到了范围查询,则右边所有列都无法使用索引优化查找. 2.哈希索引:基于哈希表实现.在MySQL中,只有Memory引擎显式的支持哈希搜索.哈希查找的速度非常快,但哈希索引只包含哈希值和行指针,不存储字段值,所以不能用索引中的值来避免读取行,也不能进行排序.由于哈希

  • MySql如何查看索引并实现优化

    MySql如何查看索引并实现优化

    mysql中支持hash和btree索引.innodb和myisam只支持btree索引,而memory和heap存储引擎可以支持hash和btree索引 我们可以通过下面语句查询当前索引使用情况: show status like '%Handler_read%'; +-----------------------+-------+ | Variable_name | Value | +-----------------------+-------+ | Handler_read_first

  • MySQL 8.0 之索引跳跃扫描(Index Skip Scan)

    前言 MySQL 8.0.13开始支持 index skip scan 也即索引跳跃扫描.该优化方式支持那些SQL在不符合组合索引最左前缀的原则的情况,优化器依然能组使用组合索引. talk is cheap ,show me the code 实践 使用官方文档的例子,构造数据 mysql> CREATE TABLE t1 (f1 INT NOT NULL, f2 INT NOT NULL, PRIMARY KEY(f1, f2)); Query OK, 0 rows affected (0.

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

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

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

  • Mysql中索引和约束的示例语句

    外键 查询一个表的主键是哪些表的外键 SELECT TABLE_NAME, COLUMN_NAME, CONSTRAINT_NAME, REFERENCED_TABLE_NAME, REFERENCED_COLUMN_NAME FROM INFORMATION_SCHEMA.KEY_COLUMN_USAGE WHERE TABLE_SCHEMA = 'mydbname' AND REFERENCED_TABLE_NAME = '表名'; 导出所有外键语句 SELECT CONCAT('ALTER

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

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

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

  • 浅谈MySQL的B树索引与索引优化小结

    浅谈MySQL的B树索引与索引优化小结

    MySQL的MyISAM.InnoDB引擎默认均使用B+树索引(查询时都显示为"BTREE"),本文讨论两个问题: 为什么MySQL等主流数据库选择B+树的索引结构? 如何基于索引结构,理解常见的MySQL索引优化思路? 为什么索引无法全部装入内存 索引结构的选择基于这样一个性质:大数据量时,索引无法全部装入内存. 为什么索引无法全部装入内存?假设使用树结构组织索引,简单估算一下: 假设单个索引节点12B,1000w个数据行,unique索引,则叶子节点共占约100MB,整棵树最多20

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

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

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

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

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

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

  • MySQL索引结构详细解析

    MySQL索引结构详细解析

    目录 简介 索引结构(树) 为什么用树,而不用哈希表 BTree索引 B+Tree索引 聚簇索引与非聚簇索引 索引分类 性能分析 索引创建场景 简介 在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法.这种数据结构,就是索引. 一般来说索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上. 优点: 1.类似大学图书馆建书目索引,提高数据检索的效率,降低数据库的IO成本. 2.通过

  • MySQL中B树索引和B+树索引的区别详解

    MySQL中B树索引和B+树索引的区别详解

    目录 1.多路搜索树 2.B树-多路平衡搜索树 3.B树索引 4.B+树索引 总结 如果用树作为索引的数据结构,每查找一次数据就会从磁盘中读取树的一个节点,也就是一页,而二叉树的每个节点只存储一条数据,并不能填满一页的存储空间,那多余的存储空间岂不是要浪费了?为了解决二叉平衡搜索树的这个弊端,我们应该寻找一种单个节点可以存储更多数据的数据结构,也就是多路搜索树. 1. 多路搜索树 1.完全二叉树高度:O(log2N),其中2为对数,树每层的节点数: 2.完全M路搜索树的高度:O(logmN),其

  • Mysql InnoDB B+树索引目录项记录页管理

    Mysql InnoDB B+树索引目录项记录页管理

    目录 Mysql InnoDB B+树索引目录项记录管理 一.目录项记录页 二.当目录项记录页也变多后 三.B+ 树 Mysql InnoDB B+树索引目录项记录管理 接上一篇内容,InnoDB 的作者想到一种更灵活的方式来管理所有目录项,是什么? 一.目录项记录页 其实这些用户目录项与用户记录很像,只是目录项中的两个列记录的是主键和页号而已,那么就可以复用之前存储用户记录的数据页来存储目录项. 为了区分用户记录和目录项,仍然使用 record_type 这个属性,当值为 1 时,表示目录项记

  • MySQL数据库的事务和索引详解

    MySQL数据库的事务和索引详解

    目录 一.事务: 事务四大特性: 并发事务带来哪些问题?(隔离所导致的一些问题) 事务隔离级别有哪些? MySQL的默认隔离级别: 二.索引: 索引的作用: 索引的分类: 索引准则: 索引的数据结构: 总结 一.事务: 事务是逻辑上的一组操作,要么都成功,要么都失败! ---------------------------------- 1.SQL执行        A:1000元     -->转账200元        B:200元 2.SQL执行        A:800元       -

  • Mysql Innodb存储引擎之索引与算法

    Mysql Innodb存储引擎之索引与算法

    目录 一.概述 二.数据结构与算法 1.二分查找 2.二叉查找树和平衡二叉树 1)二叉查找树 2)平衡二叉树 三.B+树 1.B+树完整定义 2.关于 M 和 L的选定案例 四.B+树索引 1.聚集索引 2.辅助索引 五.关于 Cardinality 值 1.Cardinality定义 2.Cardinality的更新 六.B+树索引的使用 1.联合索引 2.覆盖索引 3.优化器选择不使用索引的情况 4.索引提示 5.Multi-Range Read 优化 (MRR) 6.Index Condi

  • MySQL B-tree与B+tree索引数据结构剖析

    MySQL B-tree与B+tree索引数据结构剖析

    目录 一.产生的背景 1.1 进化要求 二.B-tree 2.1 B-tree特性 三.B+tree 3.1 B+tree特性 四.结论 一.产生的背景 二叉查找树的查找时间复杂度是O(logN),整体的查询效率已经足够高了,那么为什么还会有B树和B+树的进化演进呢? 主要的原因是:二叉树可能会退化成一个线性树,造成磁盘IO次数增高的问题,当有大量的数据存储的时候,二叉查找树查询不能将所有的数据加载到内存中,只能逐一加载磁盘页,每个磁盘对应树的节点,造成大量的磁盘IO操作(最坏的情况IO次数为树

随机推荐