MySQL索引底层数据结构详情

目录
  • 一、索引类型
    • 1.B+树
    • 2.MyISAM和InnoDB的B+树索引实现方式的区别(聚簇索引和非聚簇索引)？
    • 3.非聚簇索引
    • 4.聚簇索引的优缺点
    • 5.哈希索引
    • 6.自适应哈希索引

一、索引类型

1.B+树

为什么是B+树而不是B树？

首先看看B树和B+树在结构上的区别

B树结构：

B+树：

可以看到：

  • B树在每个节点上都有卫星数据(数据表中的一行数据)，而B+树只在叶子节点上有卫星数据。这意味着相同大小的磁盘扇区，B+树可以存储的叶子节点更多，磁盘IO次数更少；同样也意味着B+树的查找效率更稳定，而B树数据查询的最快时间复杂度是O(1)。
  • B树的每个节点只出现一次，B+树的所有节点都会出现在叶子节点中。B+树的所有叶子节点形成一个升序链表，适合区间范围查找，而B树则不适合。

2.MyISAM和InnoDB的B+树索引实现方式的区别(聚簇索引和非聚簇索引)？

首先需要了解聚簇索引和非聚簇索引。

聚簇索引：

在聚簇索引中，叶子页包含了行的全部数据，节点页值包含索引列。InnoDB通过主键聚集数据，如果没有定义主键则选择一个唯一的非空索引列代替；如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。

聚簇索引的数据分布：

 在聚簇索引中，除了主键索引，还有二级索引。二级索引中的叶子节点存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”。这意味着通过二级索引查找行，存储引擎需要找到二级索引的叶子节点获得对应的主键值，然后根据这个值去聚簇索引中查找对应的行，也称为“回表”。当然，可以通过覆盖索引避免回表或者InnoDB的自适应索引能够减少这样的重复工作。

注意：聚簇索引中每一个叶子节点不止包含完整的数据行，还包括事务ID、用于事务和MVCC的回滚指针。

3.非聚簇索引

非聚簇索引的主键索引和二级索引在结构上没有什么不同，都在叶子节点上存储指向数据的物理地址的“行指针”。

聚簇索引的主键索引和二级索引：

非聚簇索引的主键索引和二级索引：

4.聚簇索引的优缺点

优点：

把相关数据保存在一起（比如用用户ID把用户的全部邮件聚集在一起），否则每次数据读取就可能导致一次磁盘IO
数据访问更快，把索引和数据保存在同一个B+树中，通常在聚簇索引中获取数据比在非聚簇索引中查找更快
使用覆盖查询可以直接利用页节点中的主键值

缺点：

如果所有数据都可以放在内存中，顺序访问不再那么必要，聚簇索引没有优势
插入速度依赖于插入顺序，随机插入会导致页分裂，造成空洞，使用OPTIMIZE TABLE重建表
每次插入、更新、删除都需要维护索引的变化，代价很高
二级索引可能比想象中大，因为在节点中包含了引用行的主键列

5.哈希索引

哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效，这意味着，哈希索引适用于等值查询。

具体实现：对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码，哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

在MySQL中，只有Memory引擎显式支持哈希索引，当然Memory引擎也支持B树索引。

注意:Memory引擎支持非唯一哈希索引，解决冲突的方式是以链表的形式存放多个哈希值相同的记录指针。

6.自适应哈希索引

InnoDB注意到某些索引值被使用得非常频繁时，会在内存中基于B+树索引之上再创建一个哈希索引，这样就让B+树索引也具有哈希索引的一些优点，比如快速的哈希查找。

到此这篇关于MySQL索引底层数据结构详情的文章就介绍到这了,更多相关MySQL索引底层数据结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 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.B+树 2.MyISAM和InnoDB的B+树索引实现方式的区别(聚簇索引和非聚簇索引)? 3.非聚簇索引 4.聚簇索引的优缺点 5.哈希索引 6.自适应哈希索引 一.索引类型 1.B+树 为什么是B+树而不是B树? 首先看看B树和B+树在结构上的区别 B树结构: B+树: 可以看到: B树在每个节点上都有卫星数据(数据表中的一行数据),而B+树只在叶子节点上有卫星数据.这意味着相同大小的磁盘扇区,B+树可以存储的叶子节点更多,磁盘IO次数更少:同样也意味着B+树的查找效

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

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

  • 一文了解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的索引是一个非常重要的知识点,也基本上是面试必考的一个技术点,所以非常重要.那你了解MySQL索引的数据结构是怎么样的吗?为什么要采用这样的数据结构? 现在化身为MySQL的架构师,一步步迭代设计出MySQL的索引结构,保证你再也忘记不了索引的结构了,轻松通过面试. 索引介绍 MySQL表中存储的数据量非常大,

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

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

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

  • Oracle 11g Release (11.1) 索引底层的数据结构

    Oracle 11g Release (11.1) 索引底层的数据结构

    本文内容 B-树(B-tree) 散列(Hash) k-d 树(k-d tree) 点四叉树(Point Quadtree) 本文介绍关于 Oracle 索引的结构.大概了解 Oracle 索引底层的数据结构,从而更好地理解 Oracle 索引对增.删.改.查的性能. B-树(B-tree) 非索引的结构能满足所有需要,但自平衡的 B-树索引结构更能优化在大数据集上检索的性能.每个 B-树节点拥有多个键和指针.特定 B-树支持的一个节点中键的最大数量是那颗树的顺序.每个节点都具有一个潜在的 or

  • 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索引分类 索引创建语法 1.创建索引 2.查看索引 3.删除索引 4.为 username和password创建联合索引 5.给user表添加一个info的字段,并为这个字段添加全文索引 已经存在的表创建.删除索引等 1.使用ALTER TABLE语句创建索引 2.使用ALTER TABLE语句删除索引 常用的索引设计原则 索引失效情况总结 尽量使用覆盖索引 前言 索引对有一定开发经验的同学来说并不陌生,合理使用索引,能大大提升sql查询的性能,可以这么

随机推荐