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

目录
  • 索引介绍
  • B+树索引
    • 优点
    • 缺点
  • 哈希索引
    • 优点
    • 缺点
  • 补充：二者区别
  • 总结

索引介绍

索引是一种特殊的数据库结构，被设计用来快速查询数据库表中的特定记录。索引有多种类型，就像字典有拼音查找和偏旁查找一样都是为了提高检索效率。MySQL中最常见的索引类型有B+树索引 和 哈希索引，下面来简单介绍一下这两种索引类型有哪些差别和优劣。

B+树索引

B+树索引是一种多路径的平衡搜索树，具有如下特点：

  • 1.非叶子节点不保存数据，只保存索引值
  • 2.叶子节点保存所有的索引值和数据
  • 3.同级节点通过指针自小而大顺序链接
  • 4.节点内的数据也是自小而大顺序存放
  • 5.叶子节点拥有父节点的所有信息

结构如下图：

优点

  • 由于数据顺序存放，所以无论是区间还是顺序扫描都更快。
  • 非叶子节点不存储数据，因此几乎都能放在内存中，搜索效率更高
  • 单节点中可存储的数据更多，平均扫描I/O请求树更少
  • 平均查询效率稳定（每次查询都从根结点到叶子结点，查询路径长度相同）

缺点

  • 新增数据不是按顺序递增时，索引树需要重新排列，容易造成碎片和页分裂情况。

哈希索引

哈希索引采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快，具有如下特点：

  • 1.哈希索引建立在哈希表的基础上
  • 2.对于每个值，需要先计算出对应的哈希码（Hash Code），不同值的哈希码唯一
  • 3.把哈希码保存在哈希表中，同时哈希表也保存指向对应每行记录的指针

结构如下图：

优点

  • 大量唯一等值查询时，哈希索引效率通常更高。

缺点

  • 哈希索引对于范围查询和模糊匹配查询显得无能为力。
  • 哈希索引不支持排序操作，对于多列联合索引的最左匹配规则也不支持。
  • 哈希索引不支持前缀索引，因为哈希索引始终是使用索引列的全部内容来计算哈希值。
  • 如果存在哈希冲突的情况，也就是不同的索引列有着相同的哈希值，这时候需要遍历链表中所有的行指针进行逐行比对，直到找到所有满足条件的行，效率较低。

补充：二者区别

备注：先说下，在MySQL文档里，实际上是把B+树索引写成了BTREE，例如像下面这样的写法：

CREATE TABLE t(
aid int unsigned not null auto_increment,
userid int unsigned not null default 0,
username varchar(20) not null default ‘',
detail varchar(255) not null default ‘',
primary key(aid),
unique key(uid) USING BTREE,
key (username(12)) USING BTREE — 此处 uname 列只创建了最左12个字符长度的部分索引
)engine=InnoDB;

B+树是一个平衡的多叉树，从根节点到每个叶子节点的高度差值不超过1，而且同层级的节点间有指针相互链接。

在B+树上的常规检索，从根节点到叶子节点的搜索效率基本相当，不会出现大幅波动，而且基于索引的顺序扫描时，也可以利用双向指针快速左右移动，效率非常高。

因此，B+树索引被广泛应用于数据库、文件系统等场景。顺便说一下，xfs文件系统比ext3/ext4效率高很多的原因之一就是，它的文件及目录索引结构全部采用B+树索引，而ext3/ext4的文件目录结构则采用Linked list, hashed B-tree、Extents/Bitmap等索引数据结构，因此在高I/O压力下，其IOPS能力不如xfs。

简单地说，哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。

从上面的图来看，B+树索引和哈希索引的明显区别是：

  • 如果是等值查询，那么哈希索引明显有绝对优势，因为只需要经过一次算法即可找到相应的键值；当然了，这个前提是，键值都是唯一的。如果键值不是唯一的，就需要先找到该键所在位置，然后再根据链表往后扫描，直到找到相应的数据；
  • 从示意图中也能看到，如果是范围查询检索，这时候哈希索引就毫无用武之地了，因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索；
  • 同理，哈希索引也没办法利用索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询（这种部分模糊查询，其实本质上也是范围查询）；
  • 哈希索引也不支持多列联合索引的最左匹配规则；
  • B+树索引的关键字检索效率比较平均，不像B树那样波动幅度大，在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。

总结

到此这篇关于MySQL B+树索引与哈希索引的文章就介绍到这了,更多相关MySQL B+树索引与哈希索引内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

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

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

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

  • 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+树索引与哈希索引详解

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

  • MySQL索引优化之适合构建索引的几种情况详解

    MySQL索引优化之适合构建索引的几种情况详解

    目录 结论 建立索引的场景 小结 结论 在where后面的过滤字段上建立索引(select/update/delete后面的where都是适用的),使用索引加快过滤效率,不用进行全表扫描 在具有唯一要求的字段上添加唯一索引,加快查询效率,查到即可直接返回 group by或者order by后面的字段添加索引,由于索引是排好序的,所以建立索引就等同于在查询之前已经是排好序了(这里需要注意建立的联合索引建立中字段的顺序,可以结合具体案例场景7进行学习) 在DISTINCT(去重字段)后面的字段添加

  • Mysql InnoDB引擎中的数据页结构详解

    Mysql InnoDB引擎中的数据页结构详解

    目录 Mysql InnoDB引擎数据页结构 一.页的简介 二.数据页的结构 三.记录在页中的存储结构 四.记录头信息 1. deleted_flag 2. min_rec_flag 3. n_owned 4. heap_no 5. record_type 6. next_record Mysql InnoDB引擎数据页结构 InnoDB 是 mysql 的默认引擎,也是我们最常用的,所以基于 InnoDB,学习页结构.而学习页结构,是为了更好的学习索引. 一.页的简介 页是 InnoDB 管理

  • MySQL使用表锁和行锁的场景详解

    MySQL使用表锁和行锁的场景详解

    目录 前言 全局锁 表级锁 表锁 元数据锁 意向锁 行级锁 总结 前言 MySQL Innodb 的锁可以说是执行引擎的并发基础了,有了锁才能保证数据的一致性.众所周知,我们都知道 Innodb 有全局锁.表级锁.行级锁三种,但你知道什么时候会用表锁,什么时候会用行锁吗? 虽然对 MySQL 的知识点挺熟悉的,但一开始看到这个问题,树哥也是有点懵,我还真没从这个角度去思考过.大家可以暂时 1 分钟思考下答案,后面我将带大家弄清楚这个问题. 对于这个问题,我只能粗略地想起一些片段,例如: 对于表级

  • MySQL order by与group by查询优化实现详解

    MySQL order by与group by查询优化实现详解

    目录 前言 where与order by满足最左匹配法则 中间断裂 大哥不在 范围失效 order by 次序相反 覆盖索引 filesort的两种算法 group by 前言 order by满足两种情况,会使用 index 方式排序: order by语句使用索引最左前列(最左匹配法则) where子句和order by子句条件列组合满足最左匹配法则(where条件使用索引的最左前缀为常量) 下面给出几个实例来说明,如下所示我们创建表并为其创建组合索引(c1,c2,c3). CREATE T

  • MySQL 设计和命令行模式下建立详解

    MySQL 设计和命令行模式下建立详解

    MySQL 设计和命令行模式下建立详解 系列文章: MySQL 设计和命令行模式下建立详解 C++利用MySQL API连接和操作数据库实例详解 1.数据表的设计 MySQL数据库管理系统(DBMS)中,包含的MySQL中定义数据字段的类型对你数据库的优化是非常重要的.MySQL支持多种类型,大致可以分为三类:数值.日期/时间和字符串(字符)类型. 下面以大学熟悉的学生选课管理系统中用到的数据库为例,来设计相应的数据表.主要有三张表:学生表,课程表和选课表. 学生表设计: 字段(Field) 类

  • mysql日志文件General_log和Binlog开启及详解

    mysql日志文件General_log和Binlog开启及详解

    目录 背景: General_log 详解 1.介绍 2.开启数据库general_log步骤 Binlog 详解 1.介绍 2.开启binlog日志 3.常用binlog日志操作命令 4.mysqlbinlog命令使用 5.binlog的三种工作模式 总结 背景: 周末归纳下mysql的日志文件,其中general_log在mysql入侵中已经用到过,binlog即将会用到.注:mysql版本为5.7.20 General_log 详解 1.介绍 开启 general log 将所有到达MyS

  • Mysql的基础使用之MariaDB安装方法详解

    Mysql的基础使用之MariaDB安装方法详解

    我首次用mysql是在ubuntu上,现在用的是linux 中的Red Hat 分支的centOS 7 ,安装时发现通常用的都是MariaDB 来代替mysql,通过资料查询发现Mariadb是mysql的其中的一种分支,由mysql的创始人带领的团队所开发的mysql分支的一种版本,因为mysql受到被Oracle收购后的日渐封闭与缓慢的更新,众多Linux发行版逐渐抛弃了这个人气开源数据库,使MySQL在各大Linux发行版中的失势由于不满MySQL被Oracle收购后的日渐封闭与缓慢的更新

  • MySql批量插入优化Sql执行效率实例详解

    MySql批量插入优化Sql执行效率实例详解 itemcontractprice数量1万左右,每条itemcontractprice 插入5条日志. updateInsertSql.AppendFormat("UPDATE itemcontractprice AS p INNER JOIN foreigncurrency AS f ON p.ForeignCurrencyId = f.ContractPriceId SET p.RemainPrice = f.RemainPrice * {0},

  • MySql在Mac上的安装与配置详解

    一.下载安装 官网下载社区版dmg安装文件: https://dev.mysql.com/downloads/mysql/ 1.执行安装文件,按步骤完成安装. 2.安装完成后终端输入: mysql --version; ----显示版本号说明正常,若显示command not found,在终端输入如下,"/usr/local/mysql/bin/mysql"为mysql默认安装路径: $ cd /usr/local/bin/ $ sudo ln -fs /usr/local/mysq

随机推荐