MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等)

这篇具有很好参考价值的文章主要介绍了MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

索引(INDEX)基本概念

索引结构分类

B+Tree树索引结构

Hash索引结构

Full-Text索引

R-Tree索引


索引(INDEX)基本概念

什么是索引

索引是帮助MySQL高效获取数据的有序数据结构

为数据库表中的某些列创建索引,就是对数据库表中某些列的值通过不同的数据结构进行排序

为列建立索引之后,数据库除了维护数据之外,还会维护满足特定查找算法的数据结构,这些数据结构以某种方式指向数据,这样就可以在这些数据结构上实现快速查询,这种数据结构就是索引

索引的作用

通过索引可以将无序的数据变为有序的数据,能够实现快速访问数据库表中的特定信息

优缺点

优点

提高数据检索的效率,降低数据库的IO成本

通过索引对数据进行排序,降低数据排序的成本,降低CPU的消耗

缺点

索引会占用空间

索引提高了表的查询效率,但是却降低了更新表的速度(Insert、Update、Delete)

索引只是一个提高效率的因素,如果MySQL有大数据量的表,就需要花时间研究最优秀的索引(即需要研究为哪些字段建立索引能够使得效率提升到最大化,因为一条查询语句只会引用到一种索引,并且一般建议一个表建立的索引数量不要超过5个)


索引结构分类

索引结构主要分为四大类

B+Tree索引-(B+树)

最常见的索引类型,大部分的存储引擎都支持此索引

Hash索引-(Hash表)

底层的数据结构是用哈希表实现的,只有精确匹配索引列的查询才有效,不支持范围查询

Full-Text索引-(倒排索引)

又名全文索引,是一种通过建立倒排索引,快速匹配文档的方式

R-Tree索引(R-Tree树)

又名空间索引,是MyISAM引擎的一个特殊索引类型,主要用于地理位置数据,使用较少

存储引擎对不同索引的支持情况(默认B+Tree索引)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

 在MySQL数据库中,支持Hash索引的是Memory引擎;而InnoDB中具有自适应Hash的功能,根据B+tree索引在指定条件下自动构建的

B+Tree树索引结构

B+Tree树是由二叉树 → 红黑树(自平衡二叉树) → B-Tree树烟花而来的,我们在介绍B+Tree树之前先介绍这三种数据结构

二叉树

二叉树的每个节点最多有两个子节点(两颗子树);并且两个子节点是有序的

以单个节点为例:左边子节点是比自身小的,右边子节点是比自身大的

缺点

  1. 大数据量的情况下,层级较深,检索速度慢
  2. 容易形成倾斜树(左倾斜或右倾斜)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

 二叉树的工作原理

 二叉树的数据插入(依次插入30、40、20、19、21、39、35)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

 二叉树的数据遍历

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

 二叉树的数据查找(查找39 、21、25)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

 二叉树的数据删除(依次删除19、39、30)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

红黑树(自平衡二叉树)

红黑树时二叉树的变种,可以解决二叉树插入数值时产生斜树的问题

任何一个节点都有颜色(红色或黑色),通过颜色来确保树在插入和删除时的平衡

根节点一定是黑色的;Null节点被认为是黑色的;每个红色节点的两个叶子节点都是黑色

每个叶子节点到根的路径上不能出现连续的红色节点

任何一个节点到达叶子节点所经过的黑节点个数必须相等

当在红黑树中进行插入和删除操作时,会通过左旋、右旋、重新着色来修复树结构,保持树的平衡

缺点

  1. 在进行大量插入和删除操作的情况下,可能会造成频繁的树重构,影响性能
  2. 红黑树的实现比较复杂,需要维护节点的颜色和平衡
  3. 红黑树本质也是二叉树,在大数据量的情况下,层级较深,检索速度会下降

红黑树的工作原理

红黑树的数据插入(依次插入30、40、20、19、21、39、35)  使用到了右旋

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

红黑树的数据遍历

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

红黑树的数据查找(查找39 、21、25)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

红黑树的数据删除(依次删除19、39、30)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B-Tree树(多路平衡查找树)

二叉树一个Node节点只能够存储一个Key和一个Value,并且只有两个子节点;而多路树相比较而言一个Node节点能够存储更多的Key和Value,能够携带更多的子节点,建树高度会比二叉树要低

B-Tree树的一个节点能够存储多少Key和Value,可以有多少个子节点通过最大度数(MAX-Degree 也称为阶数)决定

一个m阶的B-Tree树

       树中的每个节点最多有m个子节点,m-1个Key和Value(两个子树的指针夹着一个Key和Value)

       树的根节点至少有一个Key和Value,至少两个子节点

缺点

B树的叶子节点和非叶子节点都会保存数据,使得非叶子节点保存的指针量变小

如果存储大量的数据,需要增加树的高度,导致IO操作变多,查询性能变低

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B-Tree树的工作原理

B-Tree树的数据插入Max-Degree为3(依次插入30、40、20、19、21、39、35)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B-Tree树的数据遍历

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B-Tree树的数据查找(查找39 、21、25)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B-Tree树的数据删除(依次删除19、39、30)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B+Tree

B+Tree树是B-Tree树的变种,也是一种多路搜索树,定义基本与B-Tree相同

B+Tree只有叶子节点存储数据,并且所有的元素都会出现在叶子节点中,所有叶子节点形成了一个单向链表;叶子节点将数据按照大小排列,并且相邻叶子节点之间按照大小排列

非叶子节点不存储数据,只存储Key,只是起到索引的作用,在相同的数据量下,B+Tree树更加矮壮

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B+Tree树的工作原理

B+Tree树的数据插入Max-Degree为3(依次插入30、40、20、19、21、39、35)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B+Tree树的数据遍历

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B+Tree树的数据查找(查找39 、21、25)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

B+Tree树的数据删除(依次删除19、39、30)

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

MySQL的B+Tree索引结构

MySQL的索引数据结构对经典的B+Tree进行了优化,在原B+Tree的基础上,增加了一个指向相邻叶子节点的链表指针,所有叶子节点形成了一个双向链表,提高了遍历速度

MySQL在查询是根据查询条件查询对应的键值(Key),然后将键值对应数据(Value)提取出来

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

Hash索引结构

哈希索引就是采用一定的hash算法,将键值换算成新的Hash值,将哈希值映射到一个桶中,桶中存储了所有哈希值相同的数据行的指针,然后存储在Hash表中;

当查询时,MySQL会先通过哈希函数计算出查询条件的哈希值,在Hash表中查找对应的桶,然后在对应的桶中查找相应的数据行

哈希冲突

如果两个或多个键值,映射到同一个相同的槽位(桶),则他们就产生了hash冲突,通过链表解决

MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等),MySQL数据库,mysql,数据库

 特点

  1. Hash索引只能够用于对等比较(=,in等),不支持范围查询(between,>,<等)
  2. 无法利用Hash索引完成排序操作;因为Hash索引中存放的是经过Hash计算后的Hash值,此值的大小并不一定和Hash运算之前的键值完全一样
  3. Hash索引无法避免表扫描,即每次都要全表扫描;因为Hash索引是将键值通过Hash运算之后,将其结果和对应的行指针信息存放在一个Hash表中,由于不同的索引键可能存在相同的Hash值,也就是哈希冲突,所以满足某个Hash键值的数据的记录跳数,无法直接从Hash索引中直接完成查询,还是要通过访问表中的实际数据进行比较,并得到相应的结果
  4. 对于联合索引,Hash不能使用部分索引键查询(要么全部使用,要么全部不使用)
  5. Hash只需要做一次运算,就可以找到该数据所在的桶;不像树结构那样从根、叶子节点的顺序来查找;所以Hash索引的查询效率理论上是要高于B+Tree的;不过对于存在大量Hash值相同的情况下,性能不一定比B+Tree高

Full-Text索引

通过建立倒排索引(Inverted Index)构建Full-Text索引,提高数据的检索效率

倒排索引是一种将文档中的单词/汉字映射到其出现位置的数据结构,主要用来解决判断字段的值中 是否包含 某字符/汉字的问题

我们对于简单业务或者数据量小的业务,可以通过Like()关键字来判断;但是对于大数据量业务,使用Like效率会大大降低

不同存储索引对Full-Text索引的支持

在MySQL5.6版本之前,只有MYISAM存储引擎支持全文索引

在MySQL5.6版本之后,InnoDB能够支持全文索引;不过只支持对英文的全文索引,不支持中文的全文索引;后续通过内置分词器(ngram)来支持中文索引

配置ngram的最小长度

在MySQL的配置文件中添加以下字段

ft_min_word_len = 2     #此最小长度就是分词的最小长度,默认为2

即:对于一段语句,可以分为多个汉字组,每个汉字组最少都有2个汉字

    我想学习数据库  可以分词为: 我想 学习  数据库 三个组

一般不会将ngram设置的很小,如果很小的话会占用大量的空间,因此我们一般都不修改此最小长度,就默认为2

全文索引的流程

用户输入要查找的内容 → SQL执行引擎 → ngram对查找的内容进行分词 → 把分词后的词依次的去倒排索引中去查找 → 将相应的记录返回

分词器ngram在建立索引时会对字段中的值进行分词;在进行查询时也会对要查找的内容分词

R-Tree索引

构建空间索引有多种数据结构,例如四叉树、R-Tree树

在MySQL中是通过R-Tree树来构建空间索引的,是一种加快空间数据查询速度的技术

R-tree将空间数据分割成一系列矩形区域,每个节点可以表示一个矩形区域,同时可以包含其他节点或数据项。这种层级结构允许MySQL在空间查询中更快地定位所需的数据,减少搜索范围,从而提高查询性能

例如:

一个表中的某字段存储着一个地方餐馆的经纬度位置信息,现在我们需要根据我们的位置,找附近1公里的餐馆

我们可以通过计算我们的位置,找到附近1公里范围内的经纬度范围,然后查询表中的满足此经纬度的值;为了加快检索效率,我们就可以对存储经纬度位置信息的字段建立空间索引

R-Tree的构建过程——R树是把B树的思想扩展到了多维空间

1、数据划分

所有的数据项也成为对象(点、线或面)都被视为一个单独的矩形

2、构建叶子节点(叶子节点是R树的底层节点)

将划分好的矩形进行分组,并构建叶子节点;每个叶子节点包含多个对象及其对应的矩形

3、合并叶子节点

当叶子节点的数目超过了R-Tree规定的最大容量,此时R树会尝试合并相邻的叶子节点来减少树的高度和提高查询效率

4、构建非叶子节点

将合并后叶子构建为新的非叶子节点;非叶子节点也是一个矩形,包含了其所有子节点的矩形范围

5、递归构建

重复上述的操作,知道构建出整个R树的根节点(R树的最顶层节点,将包含所有的数据范围)

具体R树的构建方式可以参考以下文章

从B树、B+树、B*树谈到R 树_v_JULY_v的博客-CSDN博客https://blog.csdn.net/v_JULY_v/article/details/6530142文章来源地址https://www.toymoban.com/news/detail-633273.html

到了这里,关于MySQL索引1——索引基本概念与索引结构(B树、R树、Hash等)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【MySQL】1、MySQL数据库的基本概念

    数据库的基本概念 1.数据 2.表         将不同的记录组织在一起;用来存储具体数据 3.数据库         表的集合,是存储数据的仓库;以一定的组织方式存储的相互有关的数据集合 4.数据库管理系统         是实现对数据库资源有效组织、管理和存取的系统软件

    2024年02月11日
    浏览(60)
  • 【MySQL数据库 | 第十七篇】索引以及索引结构介绍

    目录 前言: 索引简介:  索引结构:           二叉树索引结构         Tree(普通二叉树)         B-Tree(多路平衡查找树)         B+Tree          哈希索引数据结构 总结: 在实际生活中,我们对SQL语句进行优化实际上有很大一部分都是对索引进行优化,因此对索引

    2024年02月09日
    浏览(69)
  • MySQL的基本概念(数据库类、数据模型、服务启动与连接)

    目录 数据库基础 DB和DBMS 数据库的类型 RDBMS的结构 Windows系统下MySQL的服务启动与连接 服务启动 客户端连接 Linux下MySQL的安装和配置 安装MySQL并启动服务 通过远程连接此数据库 什么是DB 将大量的数据保存起来,通过计算机加工而成的可以进行高效访问的数据集合就成为数据库

    2024年02月15日
    浏览(47)
  • java八股文面试[数据库]——MySQL索引的数据结构

    知识点: 【2023年面试】mysql索引的基本原理_哔哩哔哩_bilibili 【2023年面试】mysql索引结构有哪些,各自的优劣是什么_哔哩哔哩_bilibili

    2024年02月10日
    浏览(48)
  • MySQL数据库概念、管理以及SQL语句的基本命令操作

    数据(data) 描述事物的符号记录 包括数字,文字、图形、图像、声音、档案记录等 以“记录”形式按统一格式进行存储(记录可以看成一条记录) 表 将不同的记录组织在一起 用来存储具体数据 记录:行 字段(属性):列 以行+列的形式就组成了表(数据存储在表中) 数

    2024年02月08日
    浏览(68)
  • 数据结构与算法之美学习笔记:48 | B+树:MySQL数据库索引是如何实现的?

    本节课程思维导图: 作为一个软件开发工程师,你对数据库肯定再熟悉不过了。作为主流的数据存储系统,它在我们的业务开发中,有着举足轻重的地位。在工作中,为了加速数据库中数据的查找速度,我们常用的处理思路是,对表中数据创建索引。那你是否思考过,数据库

    2024年01月16日
    浏览(76)
  • MySQL数据库---库基本操作 以及 表结构的操作(DDL)

    目录 前言 一.数据库的操作 1.1显示当前数据库 1.2创建数据库 1.3使用数据库  1.4删除数据库  二.数据类型 2.1数值类型 2.2字符串类型 2.3日期类型 三.数据表的操作  3.1 创建表结构。  3.2查看数据库中拥有的数据表  3.3查看指定的表结构   3.4修改表结构   3.5删除表结构  

    2024年02月09日
    浏览(65)
  • 数据库基本概念

    数据库系统的核心和基础是数据模型 。一般来说,数据模型是严格定义的一组概念的集合。这些概念精确地描述了系统的静态特征、动态特征和完整性约束条件。因此 数据模型一般由数据结构、数据操作和完整性约束三部分组成 数据结构 :存储在数据库中对象类型的集合,

    2024年02月04日
    浏览(55)
  • 【数据库】基本概念

    为什么在 ANSI/SPARC 体系结构中,外模式需要设计成多个?这么做有什么好处? 外模式:单个用户所看的局部数据的逻辑结构和特征的描述,用户与数据库系统的数据接口。保证数据安全性,每个用户只能看到外模式中的数据,其余数据不可见。 重点:简洁方便,安全性,灵

    2023年04月10日
    浏览(33)
  • 数据库的基本概念

    数据库由表集合组成,它是以一定的组织方式存储的相互有关的数据集合。 表:记录:行,字段(属性):列,以行+列的形式就组成了表(数据存储在表中)。 关系数据库的表由记录组成,记录由字段组成,字段由字符或数字组成。它可以供各种用户共享,具有最小冗余度

    2024年02月10日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包