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

搞懂这个问题之前，我们首先来看一下MySQL表的存储结构，再分别对比二叉树、多叉树、B树和B+树的区别就都懂了。

MySQL的存储结构

表存储结构

单位：表>段>区>页>行

在数据库中， 不论读一行，还是读多行，都是将这些行所在的页进行加载。也就是说存储空间的基本单位是页。
一个页就是一棵树B+树的节点，数据库I/O操作的最小单位是页，与数据库相关的内容都会存储在页的结构里。

B+树索引结构

  1. 在一棵B+树中，每个节点为都是一个页，每次新建节点的时候，就会申请一个页空间
  2. 同一层的节点为之间，通过页的结构构成了一个双向链表
  3. 非叶子节点为，包括了多个索引行，每个索引行里存储索引键和指向下一层页面的指针
  4. 叶子节点为，存储了关键字和行记录，在节点内部（也就是页结构的内部）记录之间是一个单向的链表

B+树页节点结构

有以下几个特点

  1. 将所有的记录分成几个组， 每组会存储多条记录，
  2. 页目录存储的是槽（slot），槽相当于分组记录的索引，每个槽指针指向了不同组的最后一个记录
  3. 我们通过槽定位到组，再查看组中的记录

页的主要作用是存储记录，在页中记录以单链表的形式进行存储。
单链表优点是插入、删除方便，缺点是检索效率不高，最坏的情况要遍历链表所有的节点。因此页目录中提供了二分查找的方式，来提高记录的检索效率。

B+树的检索过程

我们再来看下B+树的检索过程

  1. 从B+树的根开始，逐层找到叶子节点。
  2. 找到叶子节点为对应的数据页，将数据叶加载到内存中，通过页目录的槽采用二分查找的方式先找到一个粗略的记录分组。
  3. 在分组中通过链表遍历的方式进行记录的查找。

为什么要用B+树索引

数据库访问数据要通过页，一个页就是一个B+树节点，访问一个节点相当于一次I/O操作，所以越快能找到节点，查找性能越好。
B+树的特点就是够矮够胖，能有效地减少访问节点次数从而提高性能。

下面，我们来对比一个二叉树、多叉树、B树和B+树。

二叉树

二叉树是一种二分查找树，有很好的查找性能，相当于二分查找。
但是当N比较大的时候，树的深度比较高。数据查询的时间主要依赖于磁盘IO的次数，二叉树深度越大，查找的次数越多，性能越差。
最坏的情况是退化成了链表，如下图

为了让二叉树不至于退化成链表，人们发明了AVL树（平衡二叉搜索树）：任何结点的左子树和右子树高度最多相差1

多叉树

多叉树就是节点可以是M个，能有效地减少高度，高度变小后，节点变少I/O自然少，性能比二叉树好了

B树

B树简单地说就是多叉树，每个叶子会存储数据，和指向下一个节点的指针。

例如要查找9，步骤如下

  1. 我们与根节点的关键字 (17，35）进行比较，9 小于 17 那么得到指针 P1；
  2. 按照指针 P1 找到磁盘块 2，关键字为（8，12），因为 9 在 8 和 12 之间，所以我们得到指针 P2；
  3. 按照指针 P2 找到磁盘块 6，关键字为（9，10），然后我们找到了关键字 9。

B+树

B+树是B树的改进，简单地说是：只有叶子节点才存数据，非叶子节点是存储的指针；所有叶子节点构成一个有序链表

B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了

例如要查找关键字16，步骤如下

  1. 与根节点的关键字 (1，18，35) 进行比较，16 在 1 和 18 之间，得到指针 P1（指向磁盘块 2）
  2. 找到磁盘块 2，关键字为（1，8，14），因为 16 大于 14，所以得到指针 P3（指向磁盘块 7）
  3. 找到磁盘块 7，关键字为（14，16，17），然后我们找到了关键字 16，所以可以找到关键字 16 所对应的数据。

B+树与B树的不同：

  1. B+树非叶子节点不存在数据只存索引，B树非叶子节点存储数据
  2. B+树查询效率更高。B+树使用双向链表串连所有叶子节点，区间查询效率更高（因为所有数据都在B+树的叶子节点，扫描数据库 只需扫一遍叶子结点就行了），但是B树则需要通过中序遍历才能完成查询范围的查找。
  3. B+树查询效率更稳定。B+树每次都必须查询到叶子节点才能找到数据，而B树查询的数据可能不在叶子节点，也可能在，这样就会造成查询的效率的不稳定
  4. B+树的磁盘读写代价更小。B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，通常B+树矮更胖，高度小查询产生的I/O更少。

这就是MySQL使用B+树的原因，就是这么简单！

以上就是mysql 使用B+树索引有哪些优势的详细内容，更多关于MySQL 使用B+树索引的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • MySQL8.0中的降序索引

    前言 相信大家都知道,索引是有序的:不过,在MySQL之前版本中,只支持升序索引,不支持降序索引,这会带来一些问题:在最新的MySQL 8.0版本中,终于引入了降序索引,接下来我们就来看一看. 降序索引 单列索引 (1)查看测试表结构 mysql> show create table sbtest1\G *************************** 1. row *************************** Table: sbtest1 Create Table: CREAT

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

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

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

  • 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 全文索引的原理与缺陷

    MySQL全文索引一种特殊的索引,它会把某个数据表的某个数据列出现过的所有单词生成一份清单. alter table tablename add fulltext(column1,column2) 说明: 只能在MyISAM数据表中创建 全文索引是以空格或标点隔开才能搜到的,搜中文是搜不到(有专门的应用支持中文分词可以搜中文,但都不理想) 少于3个字符的单词不会被包含在全文索引里,可以通过修改my.cnf修改选项 ft_min_word_len=3 重新启动MySQL服务器,用repair ta

  • MySQL索引失效的几种情况详析

    MySQL索引失效的几种情况详析

    1.前导模糊查询不能利用索引(like '%XX'或者like '%XX%') 假如有这样一列code的值为'AAA','AAB','BAA','BAB' ,如果where code like '%AB'条件,由于前面是 模糊的,所以不能利用索引的顺序,必须一个个去找,看是否满足条件.这样会导致全索引扫描或者全表扫 描.如果是这样的条件where code like 'A % ',就可以查找CODE中A开头的CODE的位置,当碰到B开头的 数据时,就可以停止查找了,因为后面的数据一定不满足要求.

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

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

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

  • Mysql 5.6 "隐式转换"导致的索引失效和数据不准确的问题

    Mysql 5.6 "隐式转换"导致的索引失效和数据不准确的问题

    背景 在一次进行SQl查询时,我试着对where条件中vachar类型的字段去掉单引号查询,这个时候发现这条本应该很快的语句竟然很慢.这个varchar字段有一个复合索引.其中的总条数有58989,甚至不加单引号查出来的数据不是我们想要的数据. 使用的是mysql 5.6版本,innoDB引擎 实际情况如下 下面我们来看一下执行的结果 在上面的描述中我们还得注意就是,你的where条件的字符串不加单引号必须是全数字.不然就会报错 还有可能查出来的数据不是我们想要的数据.如下图 分析 从执行结果来

  • 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性能优化之索引优化

    mysql性能优化之索引优化

    作为免费又高效的数据库,mysql基本是首选.良好的安全连接,自带查询解析.sql语句优化,使用读写锁(细化到行).事物隔离和多版本并发控制提高并发,完备的事务日志记录,强大的存储引擎提供高效查询(表记录可达百万级),如果是InnoDB,还可在崩溃后进行完整的恢复,优点非常多.即使有这么多优点,仍依赖人去做点优化,看书后写个总结巩固下,有错请指正. 完整的mysql优化需要很深的功底,大公司甚至有专门写mysql内核的,sql优化攻城狮,mysql服务器的优化,各种参数常量设定,查询语句优化,主

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

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

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

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

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

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

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

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

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

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

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

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

  • MySQL优化中B树索引知识点总结

    为什么要进行SQL优化呢?很显然,当我们去写sql语句时: 1会发现性能低 2.执行时间太长, 3.或等待时间太长 4.sql语句欠佳,以及我们索引失效 5.服务器参数设置不合理 SQL语句执行过程分析 1.编写过程: 编写过程就是我们平常写sql语句的过程,也可以理解为编写顺序,以下就是我们编写顺序: select from join on where 条件 group by 分组 having过滤组 order by排序 limit限制查询个数 我们虽然是这样去写的,但是它mysql的引擎去

  • 关于MySQL B+树索引与哈希索引详解

    关于MySQL B+树索引与哈希索引详解

    目录 索引介绍 B+树索引 优点 缺点 哈希索引 优点 缺点 补充:二者区别 总结 索引介绍 索引是一种特殊的数据库结构,被设计用来快速查询数据库表中的特定记录.索引有多种类型,就像字典有拼音查找和偏旁查找一样都是为了提高检索效率.MySQL中最常见的索引类型有B+树索引 和 哈希索引,下面来简单介绍一下这两种索引类型有哪些差别和优劣. B+树索引 B+树索引是一种多路径的平衡搜索树,具有如下特点: 1.非叶子节点不保存数据,只保存索引值 2.叶子节点保存所有的索引值和数据 3.同级节点通过指针

  • Mysql InnoDB中B+树索引使用注意事项

    Mysql InnoDB中B+树索引使用注意事项

    目录 一.根页面万年不动 二.内节点中目录项记录的唯一性 三.一个页面至少容纳 2 条记录 一.根页面万年不动 在之前的文章里,为了方便理解,都是先画存储用户记录的叶子节点,然后再画出存储目录项记录的内节点. 但实际上 B+ 树的行成过程是这样的: 每当为某个表创建一个 B+ 树索引,都会为这个索引创建一个根节点页面.最开始表里没数据,所以根节点中既没有用户记录,也没有目录项记录. 当往表里插入用户记录时,先把用户记录存储到这个根节点上. 当根节点页空间用完,继续插入记录,此时会将根节点中所有记

  • 正确理解Mysql中的列索引和多列索引

    Mysql数据库提供两种类型的索引,如果没正确设置,索引的利用效率会大打折扣却完全不知问题出在这. 复制代码 代码如下: CREATE TABLE test (    id         INT NOT NULL,    last_name  CHAR(30) NOT NULL,    first_name CHAR(30) NOT NULL,    PRIMARY KEY (id),    INDEX name (last_name,first_name)); 以上创建的其实是一个多列索引,

随机推荐