MySQL索引和存储引擎

MySQL索引

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

索引数据结构&＃xff0c;主要包含以下几类&＃xff0c;我们来对比下

• 二叉树
• 平衡二叉树
• 红黑树
• Hash表
• B-Tree

二叉树

**定义&＃xff1a;**每个结点最多有两个子树&＃xff0c;左子树比父节点小&＃xff0c;右子树比父节点大。

缺点&＃xff1a;会出现极端情况导致整棵树只有左子树或只有右子树。

平衡二叉树

定义&＃xff1a;平衡二叉树又称AVL树&＃xff0c;是一种特殊的二叉查找树&＃xff0c;其左右子数都是平衡二叉树&＃xff0c;且左右子树高度差的绝对值不超过1。

缺点&＃xff1a;AVL树是高度平衡的&＃xff0c;频繁的插入和删除&＃xff0c;会引起频繁的rebalance&＃xff0c;导致效率下降。

红黑树

定义&＃xff1a;

• 性质1. 节点是红色或黑色。
• 性质2. 根节点是黑色。
• 性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

缺点&＃xff1a;数据量大会导致树层数比较多&＃xff0c;这样就会造成查找数据慢。

Hash表

定义&＃xff1a;散列表&＃xff08;Hash table&＃xff0c;也叫哈希表&＃xff09;&＃xff0c;是根据关键码值(Key value)而直接进行访问的数据结构。也就是说&＃xff0c;它通过把关键码值映射到表中一个位置来访问记录&＃xff0c;以加快查找的速度。这个映射函数叫做散列函数&＃xff0c;存放记录的数组叫做散列表。 对目标值进行hash运算得到hash值和数据磁盘指针地址保存到hash表&＃xff0c;这样就达到快速定位数据位置。

缺点&＃xff1a;精确查找十分快速&＃xff0c;但范围查找就碰壁了。

BTree

定义&＃xff1a;

• 一个节点可以存储多个数据&＃xff0c;这样可以避免黑红树的缺点&＃xff0c;树的层数很变小&＃xff1b;
• 叶节点具有相同的深度&＃xff0c;叶节点的指针为空&＃xff1b;
• 所有索引元素不重复&＃xff1b;
• 节点中的数据索引从左到右递增排列。

缺点&＃xff1a;节点里面数组数据&＃xff1a;每个数据的结构&＃61;索引数据&＃43;数据记录&＃xff08;即叶子节点存储键值和数据记录&＃xff09;。

每个节点占用一个盘块的磁盘空间&＃xff0c;一个节点上有两个升序排序的关键字和三个指向子树根节点的指针&＃xff0c;指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例&＃xff0c;关键字为17和35&＃xff0c;P1指针指向的子树的数据范围为小于17&＃xff0c;P2指针指向的子树的数据范围为17~35&＃xff0c;P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程&＃xff1a;

1. 根据根节点找到磁盘块1&＃xff0c;读入内存。【磁盘I/O操作第1次】

   比较关键字29在区间&＃xff08;17,35&＃xff09;&＃xff0c;找到磁盘块1的指针P2。

2. 根据P2指针找到磁盘块3&＃xff0c;读入内存。【磁盘I/O操作第2次】

   比较关键字29在区间&＃xff08;26,30&＃xff09;&＃xff0c;找到磁盘块3的指针P2。

3. 根据P2指针找到磁盘块8&＃xff0c;读入内存。【磁盘I/O操作第3次】

   在磁盘块8中的关键字列表中找到关键字29。

分析上面过程&＃xff0c;发现需要3次磁盘I/O操作&＃xff0c;和3次内存查找操作。由于内存中的关键字是一个有序表结构&＃xff0c;可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数&＃xff0c;使每次磁盘I/O取到内存的数据都发挥了作用&＃xff0c;从而提高了查询效率。

B&＃43;Tree

定义&＃xff1a;B&＃43;Tree是在B-Tree基础上的一种优化。节点里面数组数据&＃xff1a;每个数据只存储键信息&＃xff0c;这样不存数据可以腾出空间放更多的键信息&＃xff0c;让树层数越小

• 非叶子节点不存储data&＃xff0c;只存储索引(冗余)&＃xff0c;可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点·用指针连接&＃xff0c;提高区间访问的性能

将上一节中的B-Tree优化&＃xff0c;由于B&＃43;Tree的非叶子节点只存储键值信息&＃xff0c;假设每个磁盘块能存储4个键值及指针信息&＃xff0c;则变成B&＃43;Tree后其结构如下图所示&＃xff1a;

通常在B&＃43;Tree上有两个头指针&＃xff0c;一个指向根节点&＃xff0c;另一个指向关键字最小的叶子节点&＃xff0c;而且所有叶子节点&＃xff08;即数据节点&＃xff09;之间是一种链式环结构。因此可以对B&＃43;Tree进行两种查找运算&＃xff1a;一种是对于主键的范围查找和分页查找&＃xff0c;另一种是从根节点开始&＃xff0c;进行随机查找

可能上面例子中只有22条数据记录&＃xff0c;看不出B&＃43;Tree的优点&＃xff0c;下面做一个推算&＃xff1a;

InnoDB存储引擎中页的大小为16KB&＃xff0c;一般表的主键类型为 INT&＃xff08;占用4个字节&＃xff09;或 BIGINT&＃xff08;占用8个字节&＃xff09;&＃xff0c;指针类型也一般为4或8个字节&＃xff0c;也就是说一个页&＃xff08;B&＃43;Tree中的一个节点&＃xff09;中大概存储16KB/(8B&＃43;8B)&＃61;1K个键值。&＃xff08;因为是估值&＃xff0c;为方便计算&＃xff0c;这里的K取值为〖10〗^{3&＃xff09;。**也就是说一个深度为3的B&＃43;Tree索引可以维护10}3 * 10^3 * 10^3 &＃61; 10亿 条记录**。

实际情况中每个节点可能不能填充满&＃xff0c;因此在数据库中&＃xff0c;B&＃43;Tree的高度一般都在2_{4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的&＃xff0c;也就是说查找某一键值的行记录时最多只需要1}3次磁盘I/O操作。

数据库中的B&＃43;Tree索引可以分为聚集索引&＃xff08;clustered index&＃xff09;和 辅助索引&＃xff08;secondary index&＃xff09;。上面的B&＃43;Tree示例图在数据库中的实现即为聚集索引&＃xff0c;聚集索引的B&＃43;Tree中的叶子节点存放的是整张表的行记录数据。

辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据&＃xff0c;而是存储相应行数据的聚集索引键&＃xff0c;即主键。当通过辅助索引来查询数据时&＃xff0c;InnoDB存储引擎会遍历辅助索引找到主键&＃xff0c;然后再通过主键在聚集索引中找到完整的行记录数据。

MySQL存储引擎

数据库存储引擎是数据库底层软件组件&＃xff0c;数据库管理系统使用数据引擎进行创建、查询、更新和删除数据操作。不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等功能&＃xff0c;使用不同的存储引擎还可以获得特定的功能。

现在许多数据库管理系统都支持多种不同的存储引擎。MySQL 的核心就是存储引擎。

• InnoDB 事务型数据库的首选引擎&＃xff0c;支持事务安全表&＃xff08;ACID&＃xff09;&＃xff0c;支持行锁定和外键。MySQL 5.5.5 之后&＃xff0c;InnoDB 作为默认存储引擎。
• MyISAM 是基于 ISAM 的存储引擎&＃xff0c;并对其进行扩展&＃xff0c;是在 Web、数据仓储和其他应用环境下最常使用的存储引擎之一。MyISAM 拥有较高的插入、查询速度&＃xff0c;但不支持事务。
• MEMORY 存储引擎将表中的数据存储到内存中&＃xff0c;为查询和引用其他数据提供快速访问。

MySQL 提供了多个不同的存储引擎&＃xff0c;包括处理事务安全表的引擎和处理非事务安全表的引擎。在 MySQL 中&＃xff0c;不需要在整个服务器中使用同一种存储引擎&＃xff0c;针对具体的要求&＃xff0c;可以对每一个表使用不同的存储引擎。

可以利用 SHOW ENGINES 语句来显示可用的数据库引擎和默认引擎。

可以根据以下的原则来选择 MySQL 存储引擎&＃xff1a;

• 如果要提供提交、回滚和恢复的事务安全&＃xff08;ACID 兼容&＃xff09;能力&＃xff0c;并要求实现并发控制&＃xff0c;InnoDB 是一个很好的选择。
• 如果数据表主要用来插入和查询记录&＃xff0c;则 MyISAM 引擎提供较高的处理效率。
• 如果只是临时存放数据&＃xff0c;数据量不大&＃xff0c;并且不需要较高的数据安全性&＃xff0c;可以选择将数据保存在内存的 MEMORY 引擎中&＃xff0c;MySQL 中使用该引擎作为临时表&＃xff0c;存放查询的中间结果。
• 如果只有 INSERT 和 SELECT 操作&＃xff0c;可以选择Archive 引擎&＃xff0c;Archive 存储引擎支持高并发的插入操作&＃xff0c;但是本身并不是事务安全的。Archive 存储引擎非常适合存储归档数据&＃xff0c;如记录日志信息可以使用 Archive 引擎。

使用下面的语句可以修改数据库临时的默认存储引擎 SET default_storage_engine&＃61;<存储引擎名 > 注意&＃xff1a;将 MySQL 数据库的临时默认存储引擎修改为 其他的存储引擎时 &＃xff0c;但是当再次重启客户端时&＃xff0c;默认存储引擎仍然是 InnoDB。

MyISAM存储引擎

数据存储形式

MyISAM采用的是索引与数据分离的形式&＃xff0c;将数据保存在三个文件中.frm 、.MYD、.MYI。

• .frm : 存储表结构
• .MYD &＃xff1a; 存储表数据
• .MYI &＃xff1a;存储表索引

锁的粒度

MyISAM不支持行锁&＃xff0c;所以读取时对表加上共享锁&＃xff0c;在写入是对表加上排他锁。由于是对整张表加锁&＃xff0c;相比InnoDB&＃xff0c;在并发写入时效率很低。

事务

MyISAM不支持事务

数据的存储特点

MyISAM是基于非聚簇索引进行存储的。

索引实现

MyISAM索引文件和数据文件是分离的(非聚集)

其他

MyISAM提供了大量的特性&＃xff0c;包括全文索引&＃xff0c;压缩&＃xff0c;空间函数&＃xff0c;延迟更新索引键等。

• 进行压缩后的表是不能进行修改的&＃xff0c;但是压缩表可以极大减少磁盘占用空间&＃xff0c;因此也可以减少磁盘IO&＃xff0c;从而提供查询性能。
• 全文索引&＃xff0c;是一种基于分词创建的索引&＃xff0c;可以支持复杂的查询。
• 延迟更新索引键&＃xff0c;不会将更新的索引数据立即写入到磁盘&＃xff0c;而是会写到内存中的缓冲区中&＃xff0c;只有在清除缓冲区时候才会将对应的索引写入磁盘&＃xff0c;这种方式大大提升了写入性能。

InnoDB存储引擎

数据存储形式

使用InnoDB时&＃xff0c;会将数据表分为.frm 和 .ibd 两个文件进行存储。

• .frm : 存储表结构
• .ibd : 存储表数据和索引

innodb的所有数据文件&＃xff08;后缀为ibd的文件&＃xff09;&＃xff0c;他的大小始终都是16384&＃xff08;16k&＃xff09;的整数倍

锁的粒度

InnoDB采用**MVCC(多版本并发控制)**来支持高并发&＃xff0c;InnoDB实现了四个隔离级别&＃xff0c;默认级别是REPETABLE READ&＃xff0c;并通过间隙锁策略防止幻读的出现。它的锁粒度是行锁。【MVCC在稍后会进行介绍】

事务

InnoDB是典型的事务型存储引擎&＃xff0c;并且通过一些机制和工具&＃xff0c;支持真正的热备份。

数据的存储特点

InnoDB表是基于聚簇索引建立的&＃xff0c;聚簇索引对主键的查询有很高的性能&＃xff0c;不过他的二级索引&＃xff08;非主键索引&＃xff09;必须包含主键列&＃xff0c;索引其他的索引会很大。

索引实现

InnoDB索引实现(聚簇)

• 表数据文件本身就是按B&＃43;Tree组织的一个索引结构文件
• 聚簇索引-叶节点包含了完整的数据记录
• 为什么InnoDB表必须有主键&＃xff0c;并且推荐使用整型的自增主键&＃xff1f;
• 为什么非主键索引结构叶子节点存储的是主键值&＃xff1f;(一致性和节省存储空间)

联合索引

底层数据结构&＃xff1a;

比较相等时&＃xff0c;先比较第一列的值&＃xff0c;如果相等&＃xff0c;再继续比较第二列&＃xff0c;以此类推。

最左前缀原理&＃xff1a;

使用联合索引时&＃xff0c;索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引&＃xff08;a,b,c&＃xff09;&＃xff0c;mysql会从最左边的列优先匹配&＃xff0c;如果最左边的带头大哥没有使用到&＃xff0c;在未使用覆盖索引的情况下&＃xff0c;就只能全表扫描。 联合底层数据结构思考&＃xff0c;mysql会优先以联合索引第一列匹配&＃xff0c;此后才会匹配下一列&＃xff0c;如果不指定第一列匹配的值&＃xff0c;也就无法得知下一步查询哪个节点。 另外还有一种情况&＃xff0c;如果遇到 >

问题总结

InnoDB一颗B&＃43;树可以存放多少行数据&＃xff1f;

这个问题的简单回答是&＃xff1a;约2千万。为什么是这么多呢&＃xff1f;因为这是可以算出来的。

这里我们先假设B&＃43;树高为2&＃xff0c;即存在一个根节点和若干个叶子节点&＃xff0c;那么这棵B&＃43;树的存放总记录数为&＃xff1a;根节点指针数单个叶子节点记录行数。

上文我们已经说明单个叶子节点&＃xff08;页&＃xff09;中的记录数&＃61;16K/1K&＃61;16。&＃xff08;这里假设一行记录的数据大小为1k&＃xff0c;实际上现在很多互联网业务数据记录大小通常就是1K左右&＃xff09;。

那么现在我们需要计算出非叶子节点能存放多少指针&＃xff0c;其实这也很好算&＃xff0c;我们假设主键ID为bigint类型&＃xff0c;长度为8字节&＃xff0c;而指针大小在InnoDB源码中设置为6字节&＃xff0c;这样一共14字节&＃xff0c;我们一个页中能存放多少这样的单元&＃xff0c;其实就代表有多少指针&＃xff0c;即16384/14&＃61;1170。那么可以算出一棵高度为2的B&＃43;树&＃xff0c;能存放1170*16&＃61;18720条这样的数据记录。

根据同样的原理我们可以算出一个高度为3的B&＃43;树可以存放&＃xff1a;1170* 1170 *16&＃61;21902400条这样的记录。所以在InnoDB中B&＃43;树高度一般为1-3层&＃xff0c;它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO&＃xff0c;所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

聚簇索引和非聚簇索引的区别

• 聚簇索引&＃xff1a;将数据存储与索引放到了一块&＃xff0c;索引结构的叶子节点保存了行数据
• 非聚簇索引&＃xff1a;将数据与索引分开存储&＃xff0c;索引结构的叶子节点指向了数据对应的位置

为什么InnoDB表必须有主键&＃xff0c;并且推荐使用整型的自增主键&＃xff1f;

1. 如果设置了主键&＃xff0c;那么InnoDB会选择主键作为聚集索引&＃xff0c;如果没有显式定义主键&＃xff0c;则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引、如果也没有这样的唯一索引&＃xff0c;则InnoDB会选择内置6字节长的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增)。
2. 如果表使用自增主键

那么每次插入新的记录&＃xff0c;记录就会顺序添加到当前索引节点的后续位置&＃xff0c;主键的顺序按照数据记录的插入顺序排列&＃xff0c;自动有序。当一页写满&＃xff0c;就会自动开辟一个新的页

1. 如果使用非自增主键&＃xff08;如果身份证号或学号等&＃xff09;

由于每次插入主键的值近似于随机&＃xff0c;因此每次新纪录都要被插到现有索引页得中间某个位置&＃xff0c;此时MySQL不得不为了将新记录插到合适位置而移动数据&＃xff0c;甚至目标页面可能已经被回写到磁盘上而从缓存中清掉&＃xff0c;此时又要从磁盘上读回来&＃xff0c;这增加了很多开销&＃xff0c;同时频繁的移动、分页操作造成了大量的碎片&＃xff0c;得到了不够紧凑的索引结构&＃xff0c;后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

MySQL为什么用自增作为索引比较好。而UUID索引效率比较低&＃xff1f;

聚簇索引的数据的物理存放顺序与索引顺序是一致的&＃xff0c;即&＃xff1a;只要索引是相邻的&＃xff0c;那么对应的数据一定也是相邻地存放在磁盘上的。如果主键不是自增id&＃xff0c;那么可以想象&＃xff0c;它会干些什么&＃xff0c;不断地调整数据的物理地址、分页&＃xff0c;当然也有其他一些措施来减少这些操作&＃xff0c;但却无法彻底避免。但&＃xff0c;如果是自增的&＃xff0c;那就简单了&＃xff0c;它只需要一页一页地写&＃xff0c;索引结构相对紧凑&＃xff0c;磁盘碎片少&＃xff0c;效率也高。

• 索引存储在磁盘&＃xff0c;而且树的每个节点分配的空间有大小。整型占空间比较小&＃xff0c;这样可以存放多个键值。反之然后UUID占空间比较大。
• 整型比较方便&＃xff0c;UUID比较需要先转成ASCII在进行比较。

为什么非主键索引结构叶子节点存储的是主键值&＃xff1f;&＃xff08;一致性和节省存储空间&＃xff09;

1. 减少了出现行移动或者数据页分裂时二级索引的维护工作&＃xff08;当数据需要更新的时候&＃xff0c;二级索引不需要修改&＃xff0c;只需要修改聚簇索引&＃xff0c;一个表只能有一个聚簇索引&＃xff0c;其他的都是二级索引&＃xff0c;这样只需要修改聚簇索引就可以了&＃xff0c;不需要重新构建二级索引&＃xff09;&＃xff1b;
2. 聚簇索引也称为主键索引&＃xff0c;其索引树的叶子节点中存的是整行数据&＃xff0c;表中行的物理顺序与键值的逻辑&＃xff08;索引&＃xff09;顺序相同。一个表只能包含一个聚集索引。因为索引&＃xff08;目录&＃xff09;只能按照一种方法进行排序&＃xff1b;
3. 非聚簇索引&＃xff08;普通索引&＃xff09;的叶子节点内容是主键的值。在 InnoDB 里&＃xff0c;非主键索引也被称为二级索引&＃xff08;secondary index&＃xff09;。