mysql索引机制理解总结

为了加速对表中数据行的检索而创建的一种分散存储的 数据结构 。

1）索引本质是一种数据结构，数据结构如何存储是一个问题，存储在哪里也是一个问题？

答：在一般关系型数据库当中， 索引一般是存储在硬盘 上，因为可能数据量很大，并不能把所有数据都加载到内存中。而索引使用什么类型的数据结构进行存储？ 一般情况下，mysql常用的是两种存储引擎， myisam和InnoDB ，mysql5.5之前存储引擎默认为myisam，而在5.5+使用InnoDB；他们索引默认使用的都是 B+tree数据结构 ，同时支持hash索引，b-tree索引。

2）为什么不使用哈希表或者其他二叉查找树等数据结构作为索引默认数据结构？

第一步：了解性能好的条件

因为在 mysql 关系型数据库当中都是硬盘级索引，即索引数据结构存储在硬盘， 所以存在一个从硬盘加载到内存中的IO过程，**所以第一点就是此类数据结构要保证IO加载次数少**；  
 
 其次，内存中即磁盘以分页存储形式（默认一页4K，其中mysql中有的页存储16K）而从硬盘到内存的过程中，索引的某个结点加载到内存中，为了保证查询效率，**使得结点尽可能保存多的关键字。最后就是能够支持范围查询**。
复制代码

第二步：分析优劣

哈希表：虽然能快速找到value，但是不能做范围查询，所以只能特定业务下使用此类数据结构做索引；

二叉查找树：使用二分查找的方式能够快速查找到内容，可以减少查找数据的量；但是很多时候设置的主键id都是自增的情况，如果以二叉查找树的方式存储就如下所示，需要遍历全表，即此类数据结构受其主键的 排序 方式影响，所以不选择；

平衡二叉查找树：子节点的高度差不许超过1---通过左旋转右旋转的方式平衡

问题：如何使用平衡二叉树数据结构作为mysql中的索引机制？

数据搜寻过程-----这种索引机制在关系型数据库中是硬盘级索引

一个表中针对几个字段中建立的索引是很大的，不可能全部存储在内存里，一定是存储在硬盘中；

基于平衡二叉查找树的这种数据结构建立的索引机制搜寻过程是：（如果要查找的是这个语句 select * from table where id = 8 ）

过程 ：

1.数据结构存储在硬盘上；

2.首先如果要查找id=8的结点内容；我们首先把根节点id为10的结点包含的4个模块内容（关键字，数据区，子节点引用）加载到内存中；

3.使用id=8 的 8 与这个关键字进行比对，8<10;通过左子树P1去匹配得到id=5，加载到内存中；

4.最后找到id=8 加载到内存中，然后把数据区的内容拿出来；

5.也可以在数据区存储一个位置，然后通过数据区的指针指向磁盘真正的位置，然后直接去加载出来；

3）平衡二叉树相对优点

1.减少数据量搜索；

2.解决了信息链的问题；

3.不能查找范围

4）为什么mysql用b+tree而不用平衡二叉树做索引数据结构？

缺点：

a. 搜索时IO次数过多 ；

-------比如上图中 找 id=8的结点需要3次IO加载到内存中；只有7个结点的情况下找一个数就需要3次IO 如果结点多的情况 可能需要更多IO次数。

b.节点数据内容太少

-------一页 4K-----加载一次IO 只能加载一个节点----

为了解决这种办法：

使用b tree 多路平衡查找树；

5）什么是b+tree索引

B-tree 多路平衡查找树

可以解决搜索IO次数的问题； 同时节点数据内容较多

如果是多路平衡查找树： 内存中按页存储，假设一页大小4K，然后比如从硬盘中加载一个根节点到内存中的话，除去冗余存储，一个id是int，4个字节，4k=4096字节/4个字节=512个int；所以如果多路平衡查找树的话，一次io能够加载500多个关键字。

然后支持范围查找，通过结点数据存储内容多，可以解决搜索IO次数多的问题；

例子：mysql一个页的大小16K，所以存储几百几千万数据的高度也就4-5层；

btree 绝对平衡：如何保证---- 建立索引的过程是锁表的；花费时间多；

2.mysql为什么选择B+tree作为索引机制

在根节点和支结点不会保存数据区，即使命中了 不是叶子节点会一直寻找，到最后叶子节点； 相较于B树来说，根节点和支结点不保存数据区，使得保存关键字的个数更多； 所以每次加载到内容中，如果不是叶子节点，就不用进行扫库操作；而B树每个结点都需要扫库； 磁盘一次能读到更多关键字，所以读写能力更强； 叶子节点，天然有序，链表结构，排序能力更强； 查询效率的稳定；

mysql中存储引擎是一种插件式的方式，不同的表可以用不同的存储引擎； 不同的表使用不同存储引擎，他们生成的文件都不一样

3.mysql中B+tree索引是如何落地？

1）InnoDB 存储的数据结构以及扫表方式

InnoDB：以主键为索引来组织数据的存储；主键都是聚集索引 非主键都不是聚集索引

主键索引与辅助索引有主次之分：

2）myisam 存储的数据结构以及扫表方式

mysql myisam MYI：ID MYD：data

两种对比：

4.mysql索引

1）联合索引

单列索引： create index idx_name on t(name)

联合索引： create index idx_name_phonenum on t(name,phonenum)

2）覆盖索引

从辅助索引中就能获取到需要的记录，而不需要查找聚集索引中的记录。

如果查询的列，能够通过索引项的信息可以直接返回，则称该索引为查询 SQL 的覆盖索引。

模拟一个B+树的插入