mysql专题（一）：深入理解Mysql索引底层数据结构与算法

Mysql索引

帮助MySQL高效获取数据的排好序的数据结构。

1、索引

一种为表的行提供快速查找功能的数据结构，通常通过形成表示特定列或列集 的所有值的 树结构（B 树）来实现。

InnoDB表总是有一个 代表主键的聚簇索引。它们还可以在一个或多个列上定义一个或多个二级索引。根据其结构，二级索引可以分为 部分索引、 列索引或 复合索引。

索引是查询性能的一个重要方面 。设计表、查询和索引，以允许快速查找应用程序所需的数据。理想的数据库设计在可行的情况下使用覆盖索引 ；查询结果完全根据索引计算，而不读取实际的表数据。每个 外键约束还需要一个索引，以有效地检查父表和 子表中是否存在值。

虽然 B 树索引是最常见的，但哈希索引 使用了不同类型的数据结构，如MEMORY存储引擎和InnoDB 自适应哈希索引。 R树索引用于多维信息的空间索引。

2、索引缓存

InnoDB 保存全文搜索 令牌数据的内存区域 。当在属于 FULLTEXT 索引的列中插入或更新数据时，它会缓冲数据以最大限度地减少磁盘 I/O 。当索引缓存变满时，令牌数据将写入磁盘。每个InnoDB FULLTEXT索引都有自己独立的索引缓存，其大小由配置选项控制 innodb_ft_cache_size。

3、索引条件下推

索引条件下推 (ICP) 是一种优化，WHERE如果条件的一部分可以使用索引中的字段进行评估，则将条件的一部分下推到存储引擎。ICP可以减少存储引擎必须访问基表的次数和MySQL服务器必须访问存储引擎的次数。

4、索引提示

用于覆盖优化器推荐的索引的扩展SQL语法。例如，the FORCE INDEX、USE INDEX和IGNORE INDEX子句。通常在索引列的值分布不均匀时使用，从而导致基数估计不准确。

5、索引前缀

在应用于多列的索引（称为复合索引）中，索引的初始列或前导列。引用复合索引的前 1、2、3 等列的查询可以使用该索引，即使查询没有引用索引中的所有列。

6、主要概念

常用于数据库索引的树数据结构。该结构始终保持排序，支持快速查找精确匹配（等于运算符）和范围（例如，大于、小于和BETWEEN运算符）。这种类型的索引适用于大多数存储引擎，例如InnoDB和MyISAM。

因为 B 树节点可以有很多子节点，所以 B 树与二叉树不同，二叉树每个节点只能有 2 个子节点。

与仅在存储引擎中可用的哈希索引相对MEMORY。存储MEMORY引擎也可以使用B-tree索引，MEMORY如果某些查询使用范围操作符，你应该为表选择B-tree索引。

术语 B 树的使用旨在作为索引设计的一般类别的参考。由于经典 B 树设计中不存在的复杂性，MySQL 存储引擎使用的 B 树结构可能被视为变体（主要体现在子节点数据的双向链表设计）。相关信息参考MySQL Internals Manual的InnoDBPage StructureFil Header部分。

1、B-Tree 索引特性

B 树索引可用于在使用 =、 >、 >=、 <、 <=或BETWEEN运算符的表达式中进行列比较。LIKE 如果参数 LIKE是不以通配符开头的常量字符串，索引也可用于比较。例如，以下SELECT语句使用索引：

SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%';

SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';

在第一个语句中，只考虑带有的行。在第二条语句中，只考虑带有的行。

'Patrick' <= key_col < 'Patricl''Pat' <= key_col < 'Pau'

以下SELECT语句不使用索引：

SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%';

SELECT * FROM tbl_name WHERE key_col LIKE other_col;

在第一条语句中，LIKE 值以通配符开头。在第二个语句中，LIKE值不是常量。

如果使用and 超过三个字符，MySQL 使用Turbo Boyer-Moore 算法初始化字符串的模式，然后使用该模式更快地执行搜索。 ... LIKE '%string%'string

col_name IS NULL如果已编入索引，则使用使用索引的 搜索col_name。

任何未跨越 子句AND中所有级别的 索引WHERE都不会用于优化查询。换句话说，为了能够使用索引，必须在每个 AND组中使用索引的前缀。

以下WHERE子句使用索引：

... WHERE index_part1=1 AND index_part2=2 AND other_column=3

/* index = 1 OR index = 2 */

... WHERE index=1 OR A=10 AND index=2

/* optimized like "index_part1='hello'" */

... WHERE index_part1='hello' AND index_part3=5

/* Can use index on index1 but not on index2 or index3 */

... WHERE index1=1 AND index2=2 OR index1=3 AND index3=3;

这些WHERE子句不 使用索引：

/* index_part1 is not used */

... WHERE index_part2=1 AND index_part3=2

/* Index is not used in both parts of the WHERE clause */

... WHERE index=1 OR A=10

/* No index spans all rows */

... WHERE index_part1=1 OR index_part2=10

有时 MySQL 不使用索引，即使索引可用。发生这种情况的一种情况是优化器估计使用索引将需要 MySQL 访问表中很大一部分行。（在这种情况下，表扫描可能会快得多，因为它需要更少的查找。）但是，如果这样的查询仅用于LIMIT检索某些行，则 MySQL 无论如何都会使用索引，因为它可以更快地找到结果中返回几行。

2、哈希索引特征

散列索引与刚刚讨论的那些有一些不同的特征：

它们仅用于使用 =orin运算符（但速度非常快）的相等比较。它们不用于比较运算符，例如 <查找值范围的运算符。依赖这种类型的单值查找的系统被称为“键值存储”；要将 MySQL 用于此类应用程序，请尽可能使用哈希索引。

优化器不能使用散列索引来加速 ORDER BY操作。（这种类型的索引不能用于按顺序搜索下一个条目。）

MySQL 无法确定两个值之间大约有多少行（范围优化器使用它来决定使用哪个索引）。如果将MyISAM或 InnoDB表更改为散列索引 MEMORY表，这可能会影响某些查询。

只能使用整个键来搜索行。（对于 B 树索引，键的任何最左边的前缀都可用于查找行。）

Mysql索引数据结构

InnoDB索引实现(聚集)

表数据文件本身就是按B+Tree组织的一个索引结构文件

聚集索引-叶节点包含了完整的数据记录

为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？

为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

Mysql索引为什么选用B+树？

1、二叉树

2、平衡二叉树

3、红黑树

4、B树

5、B+树

6、hash

7、B*树（B+树变种INNODB）

8、B*树（B+树变种MYISAM）

mysql限制

InnoDB 限制（最大表空间大小也是表的最大大小）：

一个表最多可以包含 1017 列（在 MySQL 5.6.9 中提高了之前的 1000 列限制）。虚拟生成的列包含在此限制中。

一个表最多可以包含 64 个 二级索引。

如果innodb_large_prefix启用（默认），索引键前缀限制为 3072 字节，用于使用 or 行格式InnoDB的表。如果禁用，对于任何行格式的表，索引键前缀限制为 767 字节。 innodb_large_prefix在 MySQL 5.5 中引入以禁用大索引键前缀，以与 InnoDB不支持大索引键前缀的早期版本兼容。

InnoDB对于使用 REDUNDANT or 行格式的表 ，索引键前缀长度限制为 767 字节 COMPACT。例如，您可能会 在或 列上使用超过 255 个字符的列前缀索引达到此限制，假设有一个 字符集并且每个字符最多 3 个字节。 TEXTVARCHARutf8mb3尝试使用超过限制的索引键前缀长度会返回错误。innodb_large_prefix为避免复制配置中的此类错误，如果不能在副本上启用，请避免在源上启用。

如果您在创建 MySQL 实例时通过指定选项将页面大小减小到InnoDB 8KB或 4KB ，则索引键的最大长度将按比例降低，基于 16KB 页面大小的 3072 字节限制。innodb_page_size即页大小为8KB时索引键最大长度为1536字节，页大小为4KB时为768字节。适用于索引键前缀的限制也适用于全列索引键。

多列索引最多允许 16 列。超出限制会返回错误。

ERROR 1070 (42000): Too many key parts specified; max 16 parts allowed

对于 4KB、8KB、16KB 和 32KB 页面大小，最大行大小（不包括页外存储的任何可变长度列）略小于页面的一半。例如，默认 innodb_page_size16KB 的最大行大小约为 8000 字节。但是，对于InnoDB 64KB 的页面大小，最大行大小约为 16000 字节。LONGBLOB和 LONGTEXT 列必须小于 4GB，并且包括列在内的总行大小BLOB必须 TEXT小于 4GB。

如果一行的长度小于半页，则所有行都存储在页面的本地。如果它超过半页，则选择可变长度列用于外部页外存储，直到该行适合半页，如第 14.12.2 节，“ 文件空间管理”中所述。

尽管InnoDB在内部支持大于 65,535 字节的行大小，但 MySQL 本身对所有列的组合大小施加了 65,535 的行大小限制。请参阅 第 8.4.7 节，“表列数和行大小的限制”。

在一些较旧的操作系统上，文件必须小于 2GB。这不是InnoDB限制。如果您需要一个大型系统表空间，请使用多个较小的数据文件而不是一个大型数据文件对其进行配置，或者将表数据分布在 file-per-table 和通用表空间数据文件中。

日志文件的最大组合大小InnoDB为 512GB。

最小表空间大小略大于 10MB。最大表空间大小取决于 InnoDB页面大小。

在 Windows 32 位系统上，表空间文件不能超过 4GB（缺陷号 80149）。

一个InnoDB实例最多支持 2^32 (4294967296) 个表空间，其中少量表空间保留用于撤消表和临时表。

共享表空间最多支持 2^32 (4294967296) 个表。

表空间文件的路径，包括文件名，不能超过MAX_PATHWindows 的限制。在 Windows 10 之前，MAX_PATH限制为 260 个字符。从 Windows 10 版本 1607 开始， MAX_PATH常见 Win32 文件和目录功能的限制已被删除，但您必须启用新行为。

ROW_FORMAT=COMPRESSED在 Barracuda文件格式中假定页面大小最大为 16KB 并使用 14 位指针。

mysql各种文件

如果觉得《mysql专题（一）：深入理解Mysql索引底层数据结构与算法》对你有帮助，请点赞、收藏，并留下你的观点哦！