一、innodb存储引擎结构

二、什么是索引

1 什么是索引

MySQL索引的建立对于MySQL的高效运行是很重要的，索引可以大大提高MySQL的检索速度。打个比方，如果合理的设计且使用索引的MySQL是一辆兰博基尼的话，那么没有设计和使用索引的MySQL就是一个人力三轮车。拿汉语字典的目录页（索引）打比方，我们可以按拼音、笔画、偏旁部首等排序的目录（索引）快速查找到需要的字。

索引分单列索引和组合索引。单列索引，即一个索引只包含单个列，一个表可以有多个单列索引，但这不是组合索引。组合索引，即一个索引包含多个列。创建索引时，你需要确保该索引是应用在 SQL 查询语句的条件(一般作为 WHERE 子句的条件)。实际上，索引也是一张表，该表保存了主键与索引字段，并指向实体表的记录。

上面都在说使用索引的好处，但过多的使用索引将会造成滥用。因此索引也会有它的缺点：虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行INSERT、UPDATE和DELETE。因为更新表时，MySQL不仅要保存数据，还要保存一下索引文件。建立索引会占用磁盘空间的索引文件。

2 MySQL索引

通过上面的对比测试可以看出，索引是快速搜索的关键。MySQL索引的建立对于MySQL的高效运行是很重要的。对于少量的数据，没有合适的索引影响不是很大，但是，当随着数据量的增加，性能会急剧下降。如果对多列进行索引(组合索引)，列的顺序非常重要，MySQL仅能对索引最左边的前缀进行有效的查找。

下面介绍几种常见的MySQL索引类型。

索引分单列索引和组合索引。
单列索引，即一个索引只包含单个列，一个表可以有多个单列索引，但这不是组合索引。
组合索引，即一个索引包含多个列。

一、 mysql 索引类型

1. 主键索引 PRIMARY KEY
   它是一种特殊的唯一索引，不允许有空值。一般是在建表的时候同时创建主键索引。

create table myTable(`id` int not null,`username` varchar(16) not null,
PRIMARY KEY(id)
);

当然也可以用 ALTER 命令。记住：一一个个表表只只能能有有一一个个主主键键。

2. 唯一索引 UNIQUE
   唯一索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一。可以在创建表的时
   候指定，也可以修改表结构，如：
   ALTER TABLE table_name ADD UNIQUE (column)

3. 普通索引 INDEX
   这是最基本的索引，它没有任何限制。可以在创建表的时候指定，也可以修改表结构，如：

ALTER TABLE table_name ADD INDEX index_name (column)

4. 组合索引 INDEX
   组合索引，即一个索引包含多个列。可以在创建表的时候指定，也可以修改表结构，如：

LTER TABLE table_name ADD INDEX index_name(column1, column2, column3)

5. 全文索引 FULLTEXT
   全文索引（也称全文检索）是目前搜索引擎使用的一种关键技术。它能够利用分词技术等多种算法智能分析出文本文字中关键字词的频率及重要性，然后按照一定的算法规则智能地筛选出我们想要的搜索结果。

   可以在创建表的时候指定，也可以修改表结构，如：

ALTER TABLE table_name ADD FULLTEXT (column)

三、sql-io-执行流程

1. 首先就是用户发送一条SQL通过客户端接收之后，交由解析器解析SQL创建对应的解析树之后
2. 然后优化获取对应的数据表的信息-结构
3. 获取表中对应的数据表，首先就会去缓存中读取索引的如果没有就会通过IO读取在磁盘中记录索引的信息并返回
4. 选择合适的索引：因为一个表会有很多的索引，MySQL会对于每一个索引进行相应的算法推敲然后再做相应的删选留下最为合适的索引，所以如果说索引的 数量多的话会给查询优化器带来一定的负担。
5. 因为在当前的索引为二级索引所以这个时候就会根据二级索引的btree获取到对应的id
6. 读取到所对应的id之后再通过回表查询
7. 根据主键索引获取到对应的数据的页在磁盘中的位置
8. 在获取数据之前会判断索引缓存的数据是否满足查询，然后再判断数据库缓冲池以及读缓冲区中是否
   有缓冲，如果有就返回。没有就会去执行对应的执行计 划，从磁盘中获取数据信息 Hint：可以理解为
   SQL中的一个优化标识，在优化器中如果对于一条语句分析完了

四、二叉树的解析

1. 二分查找算法与平衡二分找法

   innodb存储引擎支持的哈希索引是自适应的，innodb存储引擎会根据标的使用情况自动为表生成哈希索引，不能认为干预是否在一张表中生成哈希索引。

   b+树索引就是传统意义上的索引，这是目前关系型数据库系统中查找最为常用和最为有效的索引。B+树结构构造类似于二叉树

   二分查找法也称为折半查找法，用来查找一组有序的记录数组中的某一记录，器基本思想是：将记录按有序化排列，在查找过程中采用跳跃式方式查找，既先以 有序数列的中点位置为比较对象，如果要找的元素直销与该重点元素，则讲待查序列缩小为左半部分，否则为右半部分 。

   比如：如下的数据
   5,10,19,22,33,44,48,55,60,68
   – 5, 10, 19, 22, 33, 44, 41, 55, 7, 51 –
   现在打算查找60所在的位置。如果说我们通过顺序查找法的话，那么我们可能就需要查找9次也就是一个个去匹配的方式查找。那么二分法则是3次查找方式如下 会先从 5,10,19,22,33,44,48,55,60,68 这个数组中查找中
   间件值取整数也就是 （10 - 1） / 2 = 4.5 =》4然后用60与 33 对比发现比33大这个时候需要去查找的区间就在 44,48,55,60,68 这一范围内；取中间件值（5 - 1）/ 2 = 2 =》 2也就是与55进行对比；然后发现还是大于，那么继续往右找 （2 - 1） / 2 = 0.5 =》 0然后匹配到了，这个时候总共执行了3次；
   用PHP代码演示一下:

<?php
//二分查找法
function binSearch($arr, $search)
{
$height = count($arr)-1;$low = 0;
while ($low <= $height) {
$mid = floor(($low + $height) / 2);//获取中间数
if ($arr[$mid] == $search) {
return $mid;//返回
} elseif ($arr[$mid] < $search) {//当中间值小于所查值时，则$mid左边的值都小于$search，
此时要将$mid赋值给
$low $low = $mid + 1;
} elseif ($arr[$mid] > $search) {//中间值大于所查值,则$mid右边的所有值都大于$search,此
时要将$mid赋值给$height
$height = $mid-1;
}
}
return "查找失败";
}//顺序查找
function seqSearch($arr, $k)
{
foreach ($arr as $key => $val) {
if ($val == $k) {
return $key;
}
}
return -1;
}// 测试
$arr=array(5,10,19,22,33,44,48,55,60,68);
// echo binSearch($arr,44).'<br/>';
// echo seqSearch($arr,44).'<br/>';
?>

我们可以通过PHP代码来模拟二分查找；找出位置以及执行次数的对比作为测试 但是这个方式如果对于非规则数据就不好使比如：5,10, 19, 22, 33, 44, 41, 55, 7, 51 从中找出7所在的位置，这个时候就会发现找不到数据。所以就需要根据对应 的规则建立对应的树。 那么根据我们目前的这个数组返回的树的结构就是

五、btree索引

1. B-tree索引
   B-Tree是为磁盘等外存储设备设计的一种平衡查找树。因此在讲B-Tree之前先了解下磁盘的相关知识。
   系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。
   InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令
   查看页的大小：

mysql> show variables like "innodb_page_size";
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.02 sec)

而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key, data] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。

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

2. B+tree 索引
   B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实
   现其索引结构。

从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，
这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+Tree相对于B-Tree有几点不同：

1. 非叶子节点只存储键值信息。
2. 所有叶子节点之间都有一个链指针。
3. 数据记录都存放在叶子节点中。

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

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

六、笔记