一、基础知识的储备

1.1、局部性原理

现在，进而讨论在作业信息不全部装入主存的情况下能否保证作业的正确运行?回答是肯定的，早在1968年 P.Denning 就研究了程序执行时的局部性(principle oflocality)原理,对程序局部性原理进行研究还有Knuth(分析一组学生的Fortran程序)Tanenbaum（分析操作系统的过程)、Huck（分析通用科学计算的程序），发现程序和数据的访问都有聚集成群的倾向，在一个时间段内，仅使田其中一小部分（称空间局部性），或者最近访问过的程序代码和数据，很快又被访问的可能性很大（称时间局部性）。这只要对程序的执行进行分析就可以发现以下一些情况:

1.2、磁盘预读(预读的长度一般为页(page)的整数倍)

页是存储器的逻辑块，操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每
个存储块称为一页（在许多操作系统中，页大小通常为4k)，主存和磁盘以页为单位交换数据。

二、索引是什么

• 索引是帮助MySQL高效获取数据的数据结构
• 索引存储在文件系统中
• 索引的文件存储形式与存储引擎有关
• 索引文件的结构
  • hash
  • 二叉树
  • B树B+树

2.1、hash表的索引格式 

hash表的数据结构可以自己去百度, 这里就不赘述了!

缺点:

• 利用hash存储的话需要将所有的数据文件添加到内存，比较耗费内存空间
• 如果所有的查询都是等值查询，那么hash确实很快，但是在企业或者实际工作环境中范围查找的数据更多，而不是等值查询，因此hash就不太适合了 

2.2、二叉树和红黑树 

      

缺点:

无论是二叉树还是红黑树，都会因为树的深度过深而造成io次数变多，影响数据读取的效率

2.3、b树的索引结构

B树特点:

• 所有键值分布在整颗树中
• 搜索有可能在非叶子结点结束，在关键字全集内做一次查找,性能通近二分查找
• 每个节点最多拥有m个子树
• 根节点至少有2个子树
• 分支节点至少拥有m/2颗子树(除根节点和叶子节点外都是分支节点)
• 所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列

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

查找关键字过程:

1、根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】

2、比较关键字28在区间(16,34)，找到磁盘块1的指针P2.

2.4、B+树的索引结构

mysql索引数据结构--B+Tree

B+Tree是在BTree的基础之上做的一种优化,变化如下:

1、B+Tree每个节点可以包含更多的节点，这个做的原因有两个，第一个原因是为了降低树的高度，第二个原因是将数据范围变为多个区间,区间越多，数据检索越快

2、非叶子节点存储key,叶子节点存储key和数据

3、叶子节点两两指针相互连接(符合磁盘的预读特性)，顺序查询性能更高

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

注意:
1、InnoDB是通过B+Tree结构对主键创建索引，然后叶子节点中存储记录，如果没有主键，那么会选择唯一键，如果没有唯一键，那么会生成—个6位的row_id来作为主键

2、如果创建索引的键是其他字段，那么在叶子节点中存储的是该记录的主键，然后再通过主键索引找到对应的记录

三、索引的分类

mysql索引的五种类型:主键索引、唯一索引、普通索引和全文索引、组合索引。通过添加索引可以提高数据的读取速度，提高项目的并发能力和抗压能力。

• 主键索引

        主键是一种唯一性索引，但它必须指定为PRIMARY KEY，每个表只能有一个主键。

• 唯一索引

        索引列的所有值都只能出现一次，即必须唯一，值可以为空。

• 普通索引

        基本的索引类型，值可以为空,没有唯一性的限制。

• 全文索引

        全文索引的索引类型为FULLTEXT。全文索引何以在varchar、char、text类型的列上创建

• 组合索引

        多列值组成一个索引,专门用于组合搜索

四、MYISAM引擎和INNODB对比