一文了解mysql索引的数据结构为什么要用B+树

目录
  • 1. Hash表？No
  • 2. 二叉查找树(BST)？No
  • 3. 红黑树？No
  • 4. 平衡二叉树(AVL)？差那么二点意思
  • 5. B-tree(B-树也称B树)？差那么一点意思
  • 6. B+树

前提： 以下的一些数据结构大家需提前知道，否则看起来会比较有困难，大家也可以按照本文所提到的知识点去主动查阅学习。

1. Hash表？No

因考虑到在数据检索的过程中经常会有范围的查询（如下），而hash表不能提供这种功能。

SELECT * FROM hero WHERE age>5 AND age<20;

使用哈希算法实现的索引虽然可以做到快速检索数据，但是没办法做数据高效范围查找，因此哈希索引是不适合作为 Mysql 的底层索引的数据结构。

2. 二叉查找树(BST)？No

二叉查找树（Binary Search Tree）虽然可以达到范围搜索，但是在树的插入过程中，如果插入的数据本来就是有顺序的，那么就会形成一条链（如下），它的最坏情况是O(n)。

3. 红黑树？No

红黑树虽然看似达到了平衡状态，但是也会有极端情况存在，和上述BST树一样，虽然不会成为链状，但是红黑树会存在右倾的现象。

在数据库中的基本主键自增操作，主键一般都是数百万数千万的，如果红黑树存在这种问题，对于查找性能而言也是巨大的消耗，我们数据库不可能忍受这种无意义的等待的。

4. 平衡二叉树(AVL)？差那么二点意思

平衡二叉树，英文翻译为Balanced Binary Tree，为啥叫AVL呢？ AVL 是大学教授G.M. Adelson-Velsky 和 E.M. Landis 名称的缩写，他们提出的平衡二叉树的概念，为了纪念他们，将平衡二叉树称为 AVL树。

AVL树本质上是一颗二叉查找树，但是它又具有以下特点：

  • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
  • 左右两个子树也都是一棵平衡二叉树。

它不存在红黑树这种右倾的现象，也具备数据高效范围查找的能力，但是数据库查询数据的瓶颈在于磁盘的IO，树节点在磁盘空间中存储可能是不连续的，假设我们一次IO读取一个树的节点，此次读入内存的这页中没有其他树的节点，那么每读取一个树的节点，就要进行一次IO，这是多么消耗时间啊，所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。 磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘IO的时间；这个花费的时间成本是内存访问的十几万倍左右。 正是由于磁盘IO是非常昂贵的操作，所以计算机操作系统对此做了优化：预读；每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中。因为局部预读原理说明：当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页（page）。一页的大小与操作系统有关，一般为4k或者8k。这也就意味着读取一页内数据的时候，实际上发生了一次磁盘IO。

相关术语解释：

扇区(sector)：

  • 磁盘上的每个磁道被等分成多个弧段，这个弧段便称作扇区（sector）。
  • 扇区是磁盘物理层面的名称，它是实际发生读写的最底层。

磁盘块(IO Block)：

  • 操作系统不与扇区直接进行交互，因为一般情况下一个扇区是512byte，如果1T去用512byte进行划分，那划分的地址空间太多了，为了让操作系统能够寻址到更大的地址空间，操作系统将相邻的扇区组合在一起，形成一个块，对块进行管理。每个磁盘块可以包括 2、4、8、16、32 或 64 个扇区，这便是磁盘块（IO Block）。
  • 磁盘块是操作系统中出现的名称，文件系统读写数据的最小单位，它同时也被叫做磁盘簇。

页(page)：

  • 页是内存中出现的名称，它是内存的最小存储单位，页的大小通常为磁盘块大小的 2^n 倍。

5. B-tree(B-树也称B树)？差那么一点意思

B树是一种平衡的多叉树，B树相比于平衡二叉树(AVL)，它能够在单个节点中存储大量键，也降低了树的高度，从而减少了IO的次数。

B树的节点中存储的是数据，单个节点存储的内容还是太少了，如何让一个节点存储的内容更多呢？B+树它来了。

6. B+树

在节点中存储某段数据的首地址，并且B+树的叶子节点用了一个链表串联起来，便于范围查找。

B+树高度降低，减少了磁盘 IO。其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。

到此这篇关于一文了解mysql索引的数据结构为什么用B+树的文章就介绍到这了,更多相关mysql B+树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

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

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

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

  • 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树索引和B+树索引的区别详解

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

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

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

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

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

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

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

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

  • 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. Hash表?No 2. 二叉查找树(BST)?No 3. 红黑树?No 4. 平衡二叉树(AVL)?差那么二点意思 5. B-tree(B-树也称B树)?差那么一点意思 6. B+树 前提: 以下的一些数据结构大家需提前知道,否则看起来会比较有困难,大家也可以按照本文所提到的知识点去主动查阅学习. 1. Hash表?No 因考虑到在数据检索的过程中经常会有范围的查询(如下),而hash表不能提供这种功能. SELECT * FROM hero WHERE age>5 AND age<

  • 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索引数据结构

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

  • 深入理解 MySQL 索引底层原理

    目录 Mysql 索引底层数据结构选型 哈希表(Hash) 二叉查找树(BST) AVL 树和红黑树 B 树 5.B+树 Innodb 引擎和 Myisam 引擎的实现 MyISAM 引擎的底层实现(非聚集索引方式) Innodb 引擎的底层实现(聚集索引方式) 一步一步推导出 Mysql 索引的底层数据结构. Mysql 作为互联网中非常热门的数据库,其底层的存储引擎和数据检索引擎的设计非常重要,尤其是 Mysql 数据的存储形式以及索引的设计,决定了 Mysql 整体的数据检索性能. 我们知

  • MySQL高级篇之索引的数据结构详解

    MySQL高级篇之索引的数据结构详解

    目录 1.为什么使用索引? 2.索引的优缺点 3.InnoDB中的索引 3.1 设计索引 3.2 常见索引概念 3.2.1 聚簇索引 3.2.2 非聚簇索引 3.2.3 联合索引 4.InnoDB与MyISAM的索引对比 5.B-Tree和B+Tree的差异 总结 1.为什么使用索引? 假如给数据使用 二叉树 这样的数据结构进行存储,如下图所示 2.索引的优缺点 MySQL 官方对索引的定义为: 索引(Index )是帮助 MySQL 高效获取数据的数据结构 .索引的本质: 索引是数据结构.你可

  • MySQL索引背后的数据结构及算法原理详解

    MySQL索引背后的数据结构及算法原理详解

    摘要 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题.特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等.为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论. 文章主要内容分为三个部分. 第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础. 第二部分结合MySQL数据库中My

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

    深入解析MySQL索引数据结构

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

  • 一文搞懂MySQL索引页结构

    一文搞懂MySQL索引页结构

    目录 1.前言 2.索引页结构 2.1FileHeader 2.2PageHeader 2.3UserRecords 2.4Infimum&Supremum 2.5PageDirectory 2.6FileTrailer 3.总结 1. 前言 「页」是InnoDB管理存储空间的基本单位,也是内存和磁盘交互的基本单位.也就是说,哪怕你需要1字节的数据,InnoDB也会读取整个页的数据,下次读取的数据如果恰巧也在这个页里,就能命中缓存了.写也是一样的,写数据前要先把页加载到内存,然后在内存中修改,该

  • 一文弄懂MySQL索引创建原则

    一文弄懂MySQL索引创建原则

    目录 一.适合创建索引 1.字段的数值有唯一性限制 2.频繁作为Where查询条件的字段 3.经常Groupby和Orderby的列 4.Update.Delete的where条件列 5.Distinct字段需要创建索引 6.多表Join连接操作时,创建索引注意事项 7.使用列的类型小的创建索引 8.使用字符串前缀创建索引 9.区分度高的列适合作为索引 10.使用最频繁的列放到联合索引的左侧 11.在多个字段都要创建索引的情况下,联合索引由于单值索引 二.不适合创建索引 1.在where中使用不

  • 新手学习MySQL索引

    新手学习MySQL索引

    前言 由于MySQL的索引中最重要的数据结构就是B+树,所以前面我们先大概讲讲B+树的原理 B+ Tree 原理 1. 数据结构 B Tree 指的是 Balance Tree,也就是平衡树.平衡树是一颗查找树,并且所有叶子节点位于同一层. B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现,它具有 B Tree 的平衡性,并且通过顺序访问指针来提高区间查询的性能. 在 B+ Tree 中,一个节点中的 key 从左到右非递减排列,如果某个指针的左右相邻 key 分别是 key

随机推荐