1.什么是索引
索引（Index）是帮助MySQL高效获取数据的数据结构。
索引的本质：索引是数据结构
阿里巴巴《Java 开发手册》提出单表行数超过 500 万行或者单表容量超过 2GB，才推荐进行分库分表。
如果预计三年后的数据量根本达不到这个级别，请不要在创建表时就分库分表。
2.外存储器-磁盘
计算机一般有两种存储的方式：「内存储器」(main memory)和「外存储器」(external memory)
- 内存:读写速度非常快，但是容量很小，而且造价非常贵，在不通电的情况下会数据会丢失，不能长期存储数据；
- 外存：磁盘是相对常见的外存储设备，它是以存取时间变化不大为特征的。可以直接存取任何字符组，且容量大、速度较其它外存设备更快。
2.1 磁盘的构造
磁盘是一个扁平的圆盘(与电唱机的唱片类似)。盘面上有许多称为磁道的圆圈，数据就记录在这些磁道上。磁盘可以是单片的，也可以是由若干盘片组成的盘组，每一盘片上有两个面。
当磁盘驱动器执行读/写功能时。盘片装在一个主轴上，并绕主轴高速旋转，当磁道在读/写头(又叫「磁头」) 下通过时，就可以进行数据的读/写了。
3.索引的本质
索引」是帮助MySQL高效获取数据的「排好序」的「数据结构」
3.1索引数据结构，主要包含以下几类
- 二叉树
- 平衡二叉树
- 红黑树
- Hash表
- B-Tree
3.2 二叉树
「定义」：每个结点最多有两个子树，左子树比父节点小，右子树比父节点大。
3.3 平衡二叉树（AVL Tree）
「定义」：平衡二叉树又称AVL树，是一种特殊的二叉查找树，其左右子树都是平衡二叉树，且左右子树高度差的绝对值不超过1。
「缺点」：AVL树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降
3.4 红黑树
「定义」：
- 性质1. 节点是红色或黑色。
- 性质2. 根节点是黑色。
- 性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
「缺点」：数据量大会导致树层数比较多，这样就会造成查找数据慢。
3.5 Hash数据结构
「定义」：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 对目标值进行hash运算得到hash值和数据磁盘指针地址保存到hash表，这样就达到快速定位数据位置。
「缺点」：精确查找十分快速，但范围查找就碰壁了。
3.6 BTree
「定义」：
- 一个节点可以存储多个数据，这样可以避免黑红树的缺点，树的层数变小；
- 叶节点具有相同的深度，叶节点的指针为空；
- 所有索引元素不重复；
- 节点中的数据索引从左到右递增排列。
「缺点」：节点里面数组数据：每个数据的结构=索引数据+数据记录（即叶子节点存储键值和数据记录）。
「模拟查找关键字29的过程：」
1.根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2.比较关键字29在区间（17,35），找到磁盘块1的指针P2。
3.根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4.比较关键字29在区间（26,30），找到磁盘块3的指针P2。
5.根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
6.在磁盘块8中的关键字列表中找到关键字29。
分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。
3.7 B+Tree
「定义」：B+Tree是在B-Tree基础上的一种优化。节点里面数组数据：每个数据只存储键信息，这样不存数据可以腾出空间放更多的键信息，让树层数越小
- 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接，提高区间访问的性能
- 将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：
4.存储引擎
数据库存储引擎是数据库底层软件组件，数据库管理系统使用数据引擎进行创建、查询、更新和删除数据操作。不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等功能，使用不同的存储引擎还可以获得特定的功能。
MySQL 的核心就是存储引擎
- InnoDB 事务型数据库的首选引擎，支持事务安全表（ACID），支持行锁定和外键。MySQL 5.5.5 之后，InnoDB 作为默认存储引擎。
- MyISAM 是基于 ISAM 的存储引擎，并对其进行扩展，是在 Web、数据仓储和其他应用环境下最常使用的存储引擎之一。MyISAM 拥有较高的插入、查询速度，但不支持事务。
- MEMORY 存储引擎将表中的数据存储到内存中，为查询和引用其他数据提供快速访问。
4.1 如何选择 MySQL 存储引擎
可以根据以下的原则来选择 MySQL 存储引擎：
- 如果要提供提交、回滚和恢复的事务安全（ACID 兼容）能力，并要求实现并发控制，InnoDB 是一个很好的选择。
- 如果数据表主要用来插入和查询记录，则 MyISAM 引擎提供较高的处理效率。
- 如果只是临时存放数据，数据量不大，并且不需要较高的数据安全性，可以选择将数据保存在内存的 MEMORY 引擎中，MySQL 中使用该引擎作为临时表，存放查询的中间结果。
- 如果只有 INSERT 和 SELECT 操作，可以选择Archive 引擎，Archive 存储引擎支持高并发的插入操作，但是本身并不是事务安全的。Archive 存储引擎非常适合存储归档数据，如记录日志信息可以使用 Archive 引擎。
4.2 MyISAM存储引擎
数据存储形式
MyISAM采用的是索引与数据分离的形式，将数据保存在三个文件中.frm 、.MYD、.MYI。
.frm : 存储表结构
.MYD ：存储表数据
.MYI ：存储表索引
锁的粒度
MyISAM不支持行锁，所以读取时对表加上共享锁，在写入时对表加上排他锁。由于是对整张表加锁，相比InnoDB，在并发写入时效率很低。
事务
MyISAM不支持事务。
数据的存储特点
MyISAM是基于「非聚簇索引」进行存储的。
索引实现
MyISAM索引文件和数据文件是分离的(「非聚集」)
其他
-MyISAM提供了大量的特性，包括全文索引，压缩，空间函数，延迟更新索引键等。
进行压缩后的表是不能进行修改的，但是压缩表可以极大减少磁盘占用空间，因此也可以减少磁盘IO，从而提供查询性能。
全文索引，是一种基于分词创建的索引，可以支持复杂的查询。
延迟更新索引键，不会将更新的索引数据立即写入到磁盘，而是会写到内存中的缓冲区中，只有在清除缓冲区时候才会将对应的索引写入磁盘，这种方式大大提升了写入性能。
