IT评测·应用市场-qidao123.com技术社区

标题: MySQL数据结构和索引 [打印本页]

作者: 农民 时间: 2024-7-26 18:44
标题: MySQL数据结构和索引
一、MySQL数据结构

InnoDB引擎

MySQL默认引擎是InnoDB引擎，这个引擎的重要特点是支持事务和行锁，
数据结构

2.1 二叉树（二叉查找树）

二叉树是一种特别的树，二叉树中每个节点的度都不能大于2，就是说每个节点最多只能有左右两个子节点
当我们像二叉查找树储存数据的时候，是安装从大到小（或从小到大）的次序保存的，如许有大概会形成一个单项链表的结构，搜刮性能就会大打扣头。

为了解决均衡避免出现这种链表的结构，所以才有了均衡二叉树
2.2 均衡二叉树

均衡二叉树就能解决上面的问题

(1)非叶子节点最多拥有两个子节点
(2)非叶子节值大于左边子节点、小于右边子节点;
(3)树的左右两边的层级数相差不会大于1,
(4)没有值相等重复的节点
均衡二叉树会通过左旋右旋来均衡二叉树，避免变成单向链表结构，但过度要求均衡，会频繁的左右旋，
所以后面就出现了红黑树
2.3 红黑树

红黑树只是减少左右旋，本身还是会左旋和右旋

性子1：每个节点要么是红色，要么是黑色。
性子2：根节点是黑色。
性子3：每个叶子节点（NIL节点，也就是 NULL 节点）是黑色。
性子4：如果一个节点是红色的，则它的两个子节点都是黑色的（从每个叶子到根的全部路径上不能有两个连续的红色节点）。
性子5：从任一节点到其每个叶子的全部简单路径都包含相同数量的黑色节点。

均衡性：
- 红黑树通过上述性子确保了树的高度保持在 O(log n)，此中 n 是树中的节点数。
- 这种性子保证了红黑树的操作（查找、插入、删除）的时间复杂度为 O(log n)。
插入操作：
- 插入新节点时，新节点默认着色为红色。
- 插入后，如果破坏了红黑树的性子，需要通过旋转和重新着色来恢复性子。
- 大概的旋转操作包括左旋、右旋、左右旋和右左旋。
删除操作：
- 删除节点大概导致红黑树失去均衡。
- 删除后，需要通过旋转和重新着色来恢复性子。
- 删除操作大概涉及复杂的颜色调整和旋转。
旋转操作：
- 左旋（Left Rotation）：如果需要将一个节点的右子节点提升到更高的位置，可以举行左旋。
- 右旋（Right Rotation）：如果需要将一个节点的左子节点提升到更高的位置，可以举行右旋。
- 左右旋（Left-Right Rotation）：先对节点的左子节点举行左旋，然后对节点本身举行右旋。
- 右左旋（Right-Left Rotation）：先对节点的右子节点举行右旋，然后对节点本身举行左旋。

2.4 B-Tree（均衡多路查找树）

每一个节点都储存完备的一条数据，这是和B+Tree最显着的区别，对于范围查询服从不高。
InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单元。InnoDB存储引擎中默认每个页的大小为16KB（16384/1024），InnoDB在把磁盘数据读入到内存时会以页为基本单元

假如说：每个磁盘块的大小是1k（一个指针+一个数据节点是1k），那么一页就是有16个磁盘块，如果每次加载一页，也有16个指针，而且每个指针指向一个磁盘块（第二层），那么对于一个三层的b-树来说。能存储的节点数就是：16X16X16 = 4096

当需要查询的数据很多时，也就是十万百万级别的时候，B-Tree结构对于查询的服从就不怎么管用了，因为这个时候树的层级会很高，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数。
所以后面的B+Tree进一步优化这件事。
2.5 B+Tree

和B-Tree的重要区别是B+Tree的全部数据存储在叶子结点中，非叶子节点只存储键值信息和指针，而有数据的叶子结点会形成一个双向链表的结构，可以范围查询。

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为1000。也就是说一个深度为3的B+Tree索引可以维护1000 * 1000 * 50(最后一层每个磁盘块存多少数据节点，假设是50个) = 5千万条记载。深度一般是三到四层

特点：

全部的叶子结点中包含了全部关键字的信息，非叶子节点只存储键值信息，及指向含有这些关键字记载的指针，且叶子结点本身依关键字的大小自小而大的次序链接，全部的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B树的非终节点也包含需要查找的有效信息)
全部叶子节点之间都有一个链指针。
数据记载都存放在叶子节点中。

二、索引

什么是索引？

数据库管理系统（DBMS）中用于加快数据检索速率的一种数据结构，InnoDB用的是B+Tree的结构
特点：

占用磁盘空间
大大进步查询服从，减少磁盘IO
降低增删改的服从

索引的类型

聚簇索引（Clustered Index）：数据按照索引次序存储，每个表只能有一个聚簇索引。
非聚簇索引（Nonclustered Index）：数据和索引分开存储，一个表可以有多个非聚簇索引。
唯一索引（Unique Index）：保证索引中的键值唯一。
全文索引（Full-text Index）：用于全文搜刮，支持复杂的内容搜刮

聚簇索引和非聚簇索引

聚簇索引，每个节点都存有完备的数据
非聚簇索引，只存了Key和指针和ID
回表和索引覆盖：
回表：当查询一个或一些数据的时候，如：select * from table where name = Joker 的时候，假设索引字段是 name，非聚簇索引查到了名字，但需要的是全部的数据，这时候和根据查到ID举行聚簇索引查询，这就是回表。
索引覆盖，以上，如果是 select name from table where name = Joker，需要的数据刚好可以通过非聚簇索引查询，不需要回表，这时候就是索引覆盖。（所以MySQL优化中有一个要求是：避免利用select *）
索引失效

可以利用Explain来查询是否利用了索引
避免索引失效对于进步数据库查询性能至关重要。以下是几种常见的方法来确保索引的有效利用：
1. 最左前缀原则

全值匹配：确保 WHERE 子句中的条件与索引列的次序相匹配。
不要跳过索引列：如果索引是复合索引（多个列组成的索引），查询时应该从最左边的列开始，依次向右举行匹配，不能跳过中间的列。

2. 避免在索引列上举行操作

不要在索引列上利用函数：例如 WHERE UPPER(column) = 'value'。
不要在索引列上举行表达式操作：例如 WHERE column * 2 = 10。
避免类型转换：确保查询中的常量与索引列的数据类型同等。

3. 范围条件后的列不可用

如果利用了范围条件（如 =, BETWEEN, LIKE 开头的模式匹配等），则在范围条件之后的索引列无法被利用。

4. 利用覆盖索引

覆盖索引：当索引包含了全部需要查询的字段时，可以避免回表查询（即不需要再从主键索引中查找数据）。
减少 SELECT * 的利用：明确指定所需的列，而不是利用 SELECT *。

5. LIKE 语句的利用

避免以通配符开头：如果利用 LIKE '%value%'，则索引大概失效。但如果利用 LIKE 'value%' 或 LIKE '%value'，则索引仍可有效利用。

6. 数据类型的匹配

确保索引列和查询中的值的数据类型同等，避免隐式类型转换。

7. 避免利用 NOT IN 和 NOT EXISTS

利用 NOT IN 或 NOT EXISTS 大概会导致索引失效。可以尝试利用 LEFT JOIN 或 NOT EXISTS 结合子查询的方式代替。

8. 选择符合的数据类型

为索引列选择符合的数据类型，尤其是当有多种数据类型可以选择时，选择占用空间较小的数据类型可以节省存储空间，进步索引的服从。

9. 维护索引

定期查抄和优化索引，例如利用 ANALYZE TABLE 和 OPTIMIZE TABLE 下令。

10. 避免利用 SELECT *

明确列出需要查询的字段，减少不必要的数据传输。

11. 利用全文索引

对于全文搜刮，利用全文索引（如 FULLTEXT 索引）。

12. 限制利用 OR

当利用 OR 时，确保至少有一个条件能够利用有效的索引。

通过遵循以上原则，可以有效地避免索引失效的问题，从而提升数据库查询的性能。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)