- MyIsAm与InnoDB数据存储结构区别
- MyIsAm与InnoDB聚集索引实现原理
- 聚集索引和非聚集索引原理，区别
- 覆盖索引索引原理
问：你可以说说什么是索引或者让你说说对索引的理解吗？
千万不要像下面这么回答，这么回答和脱裤子放P没啥区别。
答：索引就像书的目录一样，可以加快数据的检索速度……，难道人家建立索引会不清楚这一点？其实面试官问你的是平衡树，说白了就是B树和B+树，Hash这些数据结构。
应该这么答：
我们在平时创建数据表的时候，在某些关系型数据库中，数据表只能有一个自增主键AUTO_INCREMENT。
我对表的的理解是这样的：
如果一个表没有加索引，数据按顺序一条一条的在磁盘上按插入顺序存储着。
如果一张表一旦加了索引，比如加了自增主键，那么表中的数据在磁盘中就不是按顺序排列的，而是变成了树状结构，也就是我们常说的平衡树，换句话说就是整个表都变成了一个索引树，也就是所谓的聚簇索引。
这也就说明白了为什么一个表只能有一个自增主键以及只能有一个聚簇索引了，因为自增主键的作用根儿上就是根据一定算法把表的数据按照一定格式转换成平衡树存放在磁盘的。所谓聚簇索引，就是指：主索引文件和数据文件为同一份文件，目前我所了解的聚簇索引只是在Innodb存储引擎中存在。
在创建表的时候，INNODB类型的表存储的是一个文件，后缀为.frm。这个文件包含了数据、表结构、索引树。在数据结构实现方式中B+Tree的叶子节点中data就是数据本身，key为主键，如果是二级索引的话，data便会指向对应的主索引。
聚集索引中表记录的排列顺序和索引的排列顺序保持一致，所以查询效率相当快。只要找到第一个索引记录的值，其余的连续性的记录也一定是连续存放的。
上图就是带有主键的表（聚集索引）的结构图。图画的不是很好，将就着看。其中树的所有节点（底部除外）的数据都是由主键字段中的数据构成，也就是通常我们指定主键的id字段。最下面部分是真正表中的数据。 假如我们执行一个SQL语句：select * from user where id=1256;
首先根据索引定位到1256这个值所在的叶结点，然后再通过叶结点取到id等于1256的数据行。 这里不讲解平衡树的运行细节，但是从上图能看出，树一共有三层，从根节点至叶节点只需要经过三次查找就能得到结果。如下图
假如一张表有一亿条数据 ，需要查找其中某一条数据，按照常规逻辑，一条一条地去匹配的话， 最坏的情况下需要匹配一亿次才能得到结果，用大O标记法就是O(n)最坏时间复杂度，这是无法接受的，而且这一亿条数据显然不能一次性读入内存供程序使用，因此，这一亿次匹配在不经缓存优化的情况下就是一亿次IO开销，以现在磁盘的IO能力和CPU的运算能力，有可能需要几个月才能得出结果 。
如果把这张表转换成平衡树结构（一棵非常茂盛和节点非常多的树），假设这棵树有10层，那么只需要10次IO开销就能查找到所需要的数据， 速度以指数级别提升，用大O标记法就是O(log n)，n是记录总树，底数是树的分叉数，结果就是树的层次数。换言之，查找次数是以树的分叉数为底，记录总数的对数。
用程序来对数表示就是Math.Log(100000000,10)，100000000是记录数，10是树的分叉数（真实环境下分叉数远不止10），结果就是查找次数，这里的结果从亿降到了个位数。因此，利用索引会使数据库查询有惊人的性能提升。
当然任何事物都是有两面的，索引能让数据库查询数据的速度提升， 同时对表的写入数据速度就会下降，原因很简单的。 因为平衡树这个结构必须一直维持在一个正确的状态，增删改数据都会改变平衡树各节点中的索引数据内容，破坏树结构。
因此，在每次数据改变时，DBMS必须去重新梳理树（索引）的结构以确保它的正确，这会带来不小的性能开销，也就是为什么索引会给查询以外的操作带来副作用的原因。
MySQL中InnoDB 的主键一定是聚集索引。如果没有定义主键，聚集索引可能是第一个不允许为 null 的唯一索引，也有可能是 row id。
其实他们俩差不多，同样都是使用平衡树作为索引的数据结构。
区别就是：非聚集索引这棵树中所有的节点都来自于表中二级索引字段。假如给user表的name字段加上索引 ， 那么索引就是由name字段中的值构成，在数据改变时， DBMS需要一直维护索引结构的正确性。如果给表中多个字段加上索引 ，那么就会出现多个独立的索引结构，每个索引（非聚集索引）互相之间不存在关联。
每次给字段建一个新索引，字段中的数据就会被复制一份出来，用于生成索引。因此，给表添加索引，会增加表的体积，占用磁盘存储空间。
非聚集索引和聚集索引的区别在于，通过聚集索引可以查到需要查找的数据，而通过非聚集索引可以查到记录对应的主键值 ，再使用主键的值通过聚集索引查找到需要的数据，如下图
聚集和非聚集索引不管以任何方式查询表，最终都会利用主键通过聚集索引来定位到数据，聚集索引（主键）是通往真实数据所在的唯一路径。
不过，有一种例外可以不使用聚集索引就能查询出所需要的数据这种非主流的方法称之为「覆盖索引」查询，也就是平时所说的复合索引或者多字段索引查询。
刚才说过了，每次给字段加一次索引，所对应的内容就会被复制出来一份。如果为一个索引指定两个字段，那么这个两个字段的内容都会被同步至索引之中。
先看下面这个SQL语句：
//建立索引createindex index_birthday on user_info(birthday);//查询生日在1991年11月1日出生用户的用户名select user_name from user_info where birthday ='1991-11-1'这句SQL语句的执行过程如下：
首先，通过非聚集索引index_birthday查找birthday等于1991-11-1的所有记录的主键ID值然后，通过得到的主键ID值执行聚集索引查找，找到主键ID值对就的真实数据（数据行）存储的位置最后， 从得到的真实数据中取得user_name字段的值返回， 也就是取得最终的结果我们把birthday字段上的索引改成双字段的覆盖索引
createindex index_birthday_and_user_name on user_info(birthday, user_name);通过非聚集索引index_birthday_and_user_name查找birthday等于1991-11-1的叶节点的内容，然而，叶节点中除了有user_name表主键ID的值以外，user_name字段的值也在里面，因此不需要通过主键ID值的查找数据行的真实所在，直接取得叶节点中user_name的值返回即可。通过这种覆盖索引直接查找的方式，可以省略不使用覆盖索引查找的后面两个步骤，大大地提高了查询性能，如下图：
覆盖索引可以完美的解决二级索引回表查询问题。但是前提是一定得注意查询时候索引的最左侧匹配原则。
使用聚集索引的查询效率要比非聚集索引的效率要高，但是如果需要频繁去改变聚集索引的值，写入性能并不高，因为需要移动对应数据的物理位置。
聚集索引两点关键信息：根据主键值创建了 B+ 树结构，每个叶子节点包含了整行数据。
注意点：mysql5.7.18新特性count(*)统计表数据数量，不在需要回表了，大大提升了统计速度在查询的时候虽然优先走非聚集索引，但是它不需要回表操作，它只需要统计非聚集索引树上的值即可！
总的来说，在MySQL中MyIsAm使用的是B+tree索引结构，叶节点的data仅仅存放的是指向数据记录的一个地址，在MyIsAm中主键索引和辅助索引没有任何区别，只是主键索引要求key是唯一的，而辅助索引的key可以重复。
在InnoDB中使用的也是B+tree索引结构，但是在实现方式来说和MyIsAm完全不通，MyIsAm的数据文件和索引文件以及表定义文件都是分开的，MyIsAm中索引文件只是存储一个指向具体数据的一个指针。但是在innodb中，Btree可以分为两种：主键索引和二级索引（也叫辅助索引）。
innodb中主键索引一定是聚集索引，表数据文件本身就是一个B+tree结构，这个树的叶节点保存了每一条记录的完整数据，这个叶节点的key就是数据的主键，innodb中二级索引保存的是索引列值以及指向主键的指针，所以我们使用覆盖索引优化其实说白了就是对MySQL的innodb索引加速的。
MyISAM引擎中leaf node存储的内容:
主键索引 ：仅仅存储行指针；二级索引：存储的也仅仅是行指针；
InnoDB引擎中leaf node存储的内容
主键索引 ：聚集索引存储完整的数据（整行数据）二级索引：存储索引列值+主键信息
更新时间：2024-10-26 16:27
