从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择

这篇具有很好参考价值的文章主要介绍了从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


       数据结构可以说是程序员常用,但大部分人不知其所以然的知识点,本文将对Hash、二叉搜索树、平衡二叉树、B-Tree、B+Tree几种数据做一下梳理和总结。
 

1、Hash 结构

 

1.1、关于 Hash 数据结构

 
Hash 本身是一个函数,又被称为散列函数,可以大幅提升检索数据的效率。

  • Hash 算法是通过某种特定性的算法(比如:MD5、SHA1、SHA2、SHA3)将输入转变为输出。相同的输入永远可以得到相同的输出,假设输入内容有微小偏差,在输出中通常会有不同的结果。

  • Hash值的长度是固定的,而输入数据的可能性是无限的,这就会出现不同的输入数据映射到了相同的Hash值,这种现象就叫Hash碰撞

  • 解决Hash碰撞的常见方案有开放寻址法和链表法。开放寻址法是在发生碰撞时,尝试寻找下一个可用的槽位来存储数据。链表法则是将映射到同一个Hash值的数据存储在一个链表中,通过链表来解决碰撞问题

  • 当链表长度过长时,查询效率会降低,此时可以将链表转换为红黑树来提高查询效率。红黑树是一种自平衡的二叉查找树,能够保证最坏情况下的查询时间复杂度为O(log n),其中n为节点数量。

从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择,MySQL,哈希算法,二叉树,Hash,B+Tree,B树,B+树,B-Tree
举例:如果想要验证两个文件是否相同,可以直接对比两个文件通过Hash函数计算出的结果,如两个文件通过Hash函数计算的结果一样,即文件相同,否则不同。

 
提高查询速度的数据结构,常见的有两类:

  • 树,例如:平衡二叉树,查询、插入、修改、删除的平均时间复杂度都是O(log2N) .
  • 哈希,例如:HashMap,查询、插入、修改、删除的平均时间复杂度都是O(1) ;(key,value)

采用 Hash 进行检索效率非常高,基本都是一次检索就能找到数据,B+Tree 需要自顶向下依次查找,多次访问节点才能找到数据,中间需要多次 I/O 操作,从效率上来将 Hash 比 B+Tree 更快

Hash 索引适用的存储引擎如表所示:

索引/存储引擎 InnoDB MyISAM Memory
Hash 索引 不支持 不支持 支持

Hash 索引的使用场景:

  • ① 当字段的重复度低,且经常需要进行等值查询时,采用 Hash 索引是个不错的选择。

  • ② Redis 存储的核心就是 Hash 表。

  • ③ InnoDB 提供自适应 Hash 索引 (Adaptive Hash Index)
     

1.2、InnoDB索引为啥不选 Hash 结构

 
Hash结构效率高,那为啥InnoDB的索引结构要设计成树型呢?

  • 原因①,Hash索引仅能满足 (=)(<>)和 in 查询。如果进行 范围查询,时间复杂度会退化为O(n),树型结构的有序特性,依然能保持 O(log2N) 的高效率。
  • 原因②,Hash索引有一个缺陷,数据的存储是没有顺序的,在 ORDER BY 的情况下,使用 Hash 索引还需要对数据重新排序。
  • 原因③,对于联合索引而言,Hash值是将联合索引键合并后一起来计算,无法对单独的一个键或几个索引键进行查询。
  • 原因④,对于等值查询而言,通常 Hash 索引的效率更高,但如果索引列的重复值很多,效率就会降低。因为当遇到 Hash 冲突时,需要遍历桶中的行指针来进行比较,找到查询的关键字,非常耗时。故 Hash 索引常不会用到重复值多的列上,比如 性别、年龄等。

 

1.3、关于InnoDB 提供自适应 Hash 索引 (Adaptive Hash Index)

 
       如果某个数据经常被访问,当满足一定条件时,会将这个数据页的地址存放到 Hash 表中,下次查询的时候,就会直接找到这个数据页所在的位置。采用自适应 Hash 索引的目的就是,方便根据 SQL 的查询条件,加速定位到叶子节点,特别是当 B+Tree 比较深,层级比较多时,自适应Hash能显著提高数据的检索效率。

 

-- 查询是否开启 自适应Hash索引,默认为 ON ,开启.
show variables like '%adaptive_hash_index%';

从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择,MySQL,哈希算法,二叉树,Hash,B+Tree,B树,B+树,B-Tree

 

2、二叉搜索树

 
如果我们利用二叉树作为索引结构,那么磁盘的IO次数和索引树的高度是相关的。

二叉搜索树(二叉查找树)的特点

  • 一个节点只能有两个子节点,也就是一个节点度不能超过2.
  • 左子节点 < 本节点;右子节点 >= 本节点,比我大的向右,比我小的向左

 

二叉搜索树的查找规则:

二叉搜索树(Binary Search Tree),搜索某个节点和插入节点的规则一样,假设搜索插入的数值为key:

  • ① 如果 key 大于根节点,则在右子树中进行查找;
  • ② 如果 key 小于根节点,则在左子树中进行查找;
  • ③ 如果 key 等于根节点,也就是找到了这个节点,返回根节点即可。
    从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择,MySQL,哈希算法,二叉树,Hash,B+Tree,B树,B+树,B-Tree

二叉查找树可能退化成一条链表,查找数据的时间复杂度为O(N),如下图:
从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择,MySQL,哈希算法,二叉树,Hash,B+Tree,B树,B+树,B-Tree

 

3、平衡二叉树(AVL树 )

 
       为解决二叉搜索树可能退化成链表的问题,就出现了平衡二叉树(Balanced Binary Tree),又称为 AVL 树(有别于 AVL 算法),它是在二叉搜索树的基础上增加了一些约束:平衡二叉树是一课空树,或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一颗平衡二叉树

       常见的平衡二叉树包含:平衡二叉搜索树红黑树数堆伸展树一般平衡二叉树指的就是平衡二叉搜索树,搜索的时间复杂度为O(log2n),数据查询的时间主要依赖于磁盘的 I/O次数,当n 越大,查询越复杂。

从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择,MySQL,哈希算法,二叉树,Hash,B+Tree,B树,B+树,B-Tree

       每访问一次节点就需要进行一次磁盘I/O操作,以上图示例来讲,需要进行4次I/O操作。虽然平衡二叉树的效率高,但是树的深度比较高时,也意味着磁盘I/O操作次数多,就会影响整体数据查询的效率。

 

4、B-Tree(B树)

 
       B树(Balance Tree)也就是多路平衡查找树,简写为 B-Tree(这里的横杠是连接符,而不是减号)。B-Tree 的高度远小于平衡二叉树的高度。B-Tree 关键点如下:

  • B-Tree 在插入、删除节点的时候,如果导致树不平衡,就通过自动调节节点的位置来保持树的自平衡

  • 关键字集合分布在整棵树中,如果一个磁块包括了x个关键字,那指针数为x+1,叶子节点和非叶子节点都存放数据。搜索有可能在非叶子节点结束。

  • 搜索性能等价于在关键字全集内做一次二分查找。

  • 对于一个M阶(每个节点最多可以包括M个子节点)的B-Tree,根节点的儿子数的范围是[2,M],且所有叶子节点位于同一层。

    从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择,MySQL,哈希算法,二叉树,Hash,B+Tree,B树,B+树,B-Tree

假设查询关键字为 8 的数据。

  • ① 与根节点的关键字26 和 36 比较,8 小于26 ,取磁块1的P1指针向下级节点查找。
  • ② 按磁块1的P1指针找到磁块2,比对关键字 6 和 21,8大于6且小于21,取取磁块2的P2指针向下级节点查找。
  • ③ 按磁块2的P2指针找到磁块6,对比磁块6的关键字8和18,找到关键字8.

       在B-Tree 的搜索中,是把数据读取出来,然后在内存中进行比较,那比较的时间可忽略不计。读取磁盘块本身需要进行I/O操作,其消耗的时间比在内存中进行比较需要的时间较多,是数据查找用时的重要因素。B-Tree相比于平衡二叉树来说,磁盘I/O操作要少效率高,只要树的高度足够低,I/O次数足够少,就可以提高查询性能

 

5、B+Tree (B+树)

 

5.1、B+Tree 结构

 
       B+Tree 是一种多路搜素树,基于B-Tree做出了改进。主流的 DBMS都支持 B+Tree 的索引方式。B+Tree相比于B-Tree在查询效率、磁盘读写性能和范围查询方面更具优势,B+Tree 比 B-Tree 更适合文件索引系统
 
从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择,MySQL,哈希算法,二叉树,Hash,B+Tree,B树,B+树,B-Tree

B+Tree和B-Tree的区别主要体现在以下三个方面:

  • 内部节点存储数据的方式:B-Tree的每个内部节点都存储数据,而B+Tree的内部节点并不存储数据,只作为索引使用,数据都存储在叶子节点上。因为B+Tree只在叶子节点存储数据,所以在查询时稳定性更好,且查询速度更快。

  • 叶子节点的链接方式:B+Tree的叶子节点之间通过指针连接,形成一个有序链表,便于进行范围查询。而B-Tree的叶子节点并没有相连,B-Tree 做范围查询时,需要通过中序遍历才能实现。在范围查询上,B+Tree 的效率比 B-Tree 高。

  • 磁盘读写性能:B+Tree相比于B-Tree,在磁盘读写性能上更有优势。这是因为B+Tree的内部节点并没有指向关键字具体信息的指针,所以其内部节点相对B-Tree更小,如果把内部节点和叶子节点存放在同一块磁盘内,那么盘块容纳的节点数目比B-Tree更多,一次性读入内存中的需要查找的关键字也就越多,相对来说IO读写次数也就降低了。
     

5.2、B+Tree 相关思考题

 
1、为了减少IO,B+Tree 索引树会一次性加载吗?

  • ① 数据库索引存储在磁盘上,如果数据量过大,必然会导致索引的大小也会很大,超过几个G.
  • ② 当利用索引查询时,是不可能将全部几个G 的索引数据,全都加载到内存中的。只能逐一加载每个磁盘页,因此磁盘页对应着索引树的节点。

 
2、B+Tree 的存储能力如何?为何说一般查找行记录,最多只需要 1~3次磁盘IO ?

InnoDB 存储引擎中数据页的大小默认为 16KB,一般表的主键类型为 int(占4个字节)或 bigint(占8个字节),指针类型一般也为4或8个字节,所以一个根节点或内节点的数据页(B+Tree中的一个节点)中大概存储 16KB/(8B+8B) = 1K 个键值。估算一下,就当K 的取值为10^3,那一个深度为3 的B+Tree 索引可以维护的数据为 10^3 * 10^3 * 10^2 = 1亿 条记录(这里假设一个叶子节点的数据页可以存 100 条行记录数据)。

实际情况中每个节点可能不会填充满,所以在数据库中,B+Tree 的高度一般都在 2~4 层。MySQL 的 InnoDB 存储引擎在设计时,将根节点常驻内存,也就是说查找某一键值的行记录时,最多只需要1~3次磁盘 IO 操作。

 
3、为什么说B+Tree 比 B-Tree 更适合实际应用中,操作系统的文件索引和数据库索引?

  • B+Tree 的磁盘读写代价更低

B+Tree 的内部节点,并没有指向关键字具体信息的指针,故其内部节点相对B-Tree 更小。通俗来说,就是B-Tree每个层级的节点都存放的行数据,但是B+Tree 只有在叶子节点存放行数据,内节点存放主键或非聚簇索引字段,所以一般情况来讲相同的数据体量,B+Tree的层级会低,磁盘IO操作次数更少,磁盘读写代价更低。

  • B+Tree 的查询效率更稳定

B+Tree 的叶子节点才会有用户记录行数据,所以任何关键字的查找,必须走一条从根节点到叶子节点的路,所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

 
4、Hash 索引和 B+Tree 索引的区别?

  • ① Hash 索引不能进行范围查询,B+Tree 可以。

  • ② Hash 索引不支持联合索引的最左原则(即联合索引的部分索引无法使用),B+Tree 可以。

  • ③ Hash 索引不支持 ORDER BY 排序,B+Tree 可以(B+Tree索引数据是有序的)。

  • ④ Hash 索引不支持模糊查询,B+Tree 使用LIKE进行模糊查询时, LIKE 后面后模糊查询(比如%结尾)可以起到优化作用。

  • ⑤ InnoDB 不支持哈希索引,但提供自适应 Hash 索引 (Adaptive Hash Index)。

 

5、Hash 索引和 B+Tree 索引是在键索引时,手动指定的吗?

对于MySQL而言,针对 InnoDB 和 MyISAM 存储引擎,都会默认采用 B+Tree 索引,无法使用 Hash 索引。InnoDB 提供的自适应 Hash 是不需要手动指定的。如果 Memory/Heap 和 NDB 存储引擎,是可以进行选择 Hash 索引的。

 
 

系列文章:

一: 《搞懂 MySql 的架构和执行流程》
二: 《从InnoDB索引的数据结构,去理解索引》
三: 《从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择》
四: 《MySQL 的索引分类和设计原则》
五: 《MySQL 优化思路篇》
六: 《理解MySQL的日志 redo、undo、binlog》
七: 《并发事务下,不同隔离级别可能出现的问题》
八: 《多维度梳理 MySQL 锁》
九: 《MySQL 之多版本并发控制 MVCC》
 
 
 
 
 
.文章来源地址https://www.toymoban.com/news/detail-715068.html

到了这里,关于从 Hash索引、二叉树、B-Tree 与 B+Tree 对比看索引结构选择的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构第四天: Complete Binary Search Tree 【搜索二叉树,完全二叉树】

     这道题需要的操作时排序并且需要遍历,最重要的一点它是个完全二叉树,所以数组是最适合的 这道题我的思路来自于浙江大学课件7.0.2完全二叉树 这道题说白就是将输入的样例构造成一个完全搜索二叉树。因为完全线索二叉树的 根节点一定是是一个处于左右子树中间的那

    2024年02月06日
    浏览(55)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(45)
  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • 数据结构与算法(三):树论(树形结构、二叉树、二叉搜索树、红黑树、Btree&B+Tree、赫夫曼树、堆树)

    树论(树形结构、二叉树、二叉搜索树、红黑树、Btree、B+Tree、赫夫曼树、堆树) 在树形结构里面重要的术语: 结点:树里面的元素。 父子关系:结点之间相连的边 子树:当结点大于1时,其余的结点分为的互不相交的集合称为子树 度:一个结点拥有的子树数量称为结点的

    2024年02月01日
    浏览(94)
  • MySQL索引为什么选择B+树,而不是二叉树、红黑树、B树?

    二叉树是一种二分查找树,有很好的查找性能,相当于二分查找。 二叉树的非叶子节值大于左边子节点、小于右边子节点。 原因: 但是当N比较大的时候,树的深度比较高。数据查询的时间主要依赖于磁盘IO的次数,二叉树深度越大,查找的次数越多,性能越差。 最坏的情况

    2024年04月25日
    浏览(43)
  • 二叉树(binary tree)

    二叉树(Binary Tree)是一种常见的树状数据结构,它由一组节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点: 每个节点最多有两个子节点,分别称为左子节点和右子节点。 左子树和右子树也是二叉树,它们的结构与父节点类似。

    2024年02月09日
    浏览(43)
  • 树(Tree)和二叉树

    目录 1.树的定义 2.一些树的定义 3.树的存储结构 4.二叉树的定义 5.满二叉树和完全二叉树 6.二叉树的性质 7.二叉树的存储方式 8.二叉树的基本操作 8.1 二叉树的4种遍历方式 8.2 二叉树的基本操作 树是一种非线性的数据结构,它表现的关系是 一对多 它是由n(n=0)个结点

    2024年02月03日
    浏览(31)
  • 平衡二叉树(Balanced Binary Tree)

    平衡二叉树是一种特殊的二叉搜索树,它具有以下特点: 每个节点的左子树和右子树的高度差不超过1。 所有的子树也都是平衡二叉树。 通过保持平衡性,平衡二叉树可以在最坏情况下仍然具有较好的性能,保证查找、插入和删除操作的时间复杂度为O(log n)。 平衡二叉树的常

    2024年02月09日
    浏览(36)
  • B-TREE(B-树)

    B-TREE B-tree 又叫平衡多路查找树。一棵 m 阶的 B-tree (m 叉树)的特性如下(其中 ceil(x)是一个取上限的函数): 树中每个结点至多有 m 个孩子; 除根结点和叶子结点外,其它每个结点至少有有 ceil(m / 2)个孩子; 若根结点不是叶子结点,则至少有 2 个孩子(特殊情况:没有孩子的

    2024年01月16日
    浏览(40)
  • Leetcode 1367. Linked List in Binary Tree (二叉树好题)

    Linked List in Binary Tree Medium Given a binary tree root and a linked list with head as the first node. Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False. In this context downward path means a path that starts at some node and goes downwards. Exampl

    2024年01月25日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包