数据库的索引
为什么要有索引
它是用于提高数据库表数据访问速度的数据库对象
- 索引可以避免全表扫描。多数查询可以仅扫描少量索引页及数据页，而不是遍历所有数据页。
- 对于非聚集索引，有些查询甚至可以不访问数据页。
- 聚集索引可以避免数据插入操作集中于表的最后一个数据页。
- 一些情况下，索引还可用于避免排序操作。
索引是怎么存储的
- 基于B树
普通的B-Tree的结点中，元素就是一个个的数字。但是上图中，我们把元素部分拆分成了key-data的形式，key就是数据的主键，data就是具体的数据。这样我们在找一条数的时候，就沿着根结点往下找就ok了，效率是比较高的。
- 基于B+树
局部性原理:
当一个数据被用到时，其附近的数据也通常会马上被使用。操作系统从磁盘读取数据到内存是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存
B-Tree和B+Tree该如何选择呢？都有哪些优劣呢？
-
B-Tree因为非叶子结点也保存具体数据，所以在查找某个关键字的时候找到即可返回。而B+Tree所有的数据都在叶子结点，每次查找都得到叶子结点。所以在同样高度的B-Tree和B+Tree中，B-Tree查找某个关键字的效率更高。
-
由于B+Tree所有的数据都在叶子结点，并且结点之间有指针连接，在找大于某个关键字或者小于某个关键字的数据的时候，B+Tree只需要找到该关键字然后沿着链表遍历就可以了，而B-Tree还需要遍历该关键字结点的根结点去搜索。
-
由于B-Tree的每个结点（这里的结点可以理解为一个数据页）都存储主键+实际数据，而B+Tree非叶子结点只存储关键字信息，而每个页的大小有限是有限的，所以同一页能存储的B-Tree的数据会比B+Tree存储的更少。这样同样总量的数据，B-Tree的深度会更大，增大查询时的磁盘I/O次数，进而影响查询效率。
innodb引擎数据存储
在InnoDB存储引擎中，也有页的概念，默认每个页的大小为16K，也就是每次读取数据时都是读取4*4k的大小！假设我们现在有一个用户表，我们往里面写数据
这里需要注意的一点是，在某个页内插入新行时，为了不减少数据的移动，通常是插入到当前行的后面或者是已删除行留下来的空间，所以在某一个页内的数据并不是完全有序的（后面页结构部分有细讲），但是为了为了数据访问顺序性，在每个记录中都有一个指向下一条记录的指针，以此构成了一条单向有序链表，不过在这里为了方便演示我是按顺序排列的！
由于数据还比较少，一个页就能容下，所以只有一个根结点，主键和数据也都是保存在根结点（左边的数字代表主键，右边名字、性别代表具体的数据）。假设我们写入10条数据之后，Page1满了，再写入新的数据会怎么存放呢？我们继续看下图：
有个叫“秦寿生”的朋友来了，但是Page1已经放不下数据了，这时候就需要进行页分裂，产生一个新的Page。在innodb中的流程是怎么样的呢？
1、产生新的Page2，然后将Page1的内容复制到Page2。 2、产生新的Page3，“秦寿生”的数据放入Page3。 3、原来的Page1依然作为根结点，但是变成了一个不存放数据只存放索引的页，并且有两个子结点Page2、Page3。 这里有两个问题需要注意的是 1、为什么要复制Page1为Page2而不是创建一个新的页作为根结点，这样就少了一步复制的开销了？ 如果是重新创建根结点，那根结点存储的物理地址可能经常会变，不利于查找。并且在innodb中根结点是会预读到内存中的，所以结点的物理地址固定会比较好！
2、原来Page1有10条数据，在插入第11条数据的时候进行裂变，根据前面对B-Tree、B+Tree特性的了解，那这至少是一颗11阶的树，裂变之后每个结点的元素至少为11/2=5个，那是不是应该页裂变之后主键1-5的数据还是在原来的页，主键6-11的数据会放到新的页，根结点存放主键6？ 如果是这样的话新的页空间利用率只有50%，并且会导致更为频繁的页分裂。所以innodb对这一点做了优化，新的数据放入新创建的页，不移动原有页面的任何记录。
随着数据的不断写入，这棵树也逐渐枝繁叶茂，如下图：
每次新增数据，都是将一个页写满，然后新创建一个页继续写，这里其实是有个隐含条件的，那就是主键自增！主键自增写入时新插入的数据不会影响到原有页，插入效率高！且页的利用率高！但是如果主键是无序的或者随机的，那每次的插入可能会导致原有页频繁的分裂，影响插入效率！降低页的利用率！这也是为什么在innodb中建议设置主键自增的原因！
这棵树的非叶子结点上存的都是主键，那如果一个表没有主键会怎么样？在innodb中，如果一个表没有主键，那默认会找建了唯一索引的列，如果也没有，则会生成一个隐形的字段作为主键！
有数据插入那就有删除，如果这个用户表频繁的插入和删除，那会导致数据页产生碎片，页的空间利用率低，还会导致树变的“虚高”，降低查询效率！这可以通过索引重建来消除碎片提高查询效率！
innodb引擎数据查找 数据插入了怎么查找呢？
1、找到数据所在的页。这个查找过程就跟前面说到的B+Tree的搜索过程是一样的，从根结点开始查找一直到叶子结点。 2、在页内找具体的数据。读取第1步找到的叶子结点数据到内存中，然后通过分块查找的方法找到具体的数据。 这跟我们在新华字典中找某个汉字是一样的，先通过字典的索引定位到该汉字拼音所在的页，然后到指定的页找到具体的汉字。innodb中定位到页后用了哪种策略快速查找某个主键呢？这我们就需要从页结构开始了解。
左边蓝色区域称为Page Directory，这块区域由多个slot组成，是一个稀疏索引结构，即一个槽中可能属于多个记录，最少属于4条记录，最多属于8条记录。槽内的数据是有序存放的，所以当我们寻找一条数据的时候可以先在槽中通过二分法查找到一个大致的位置。
右边区域为数据区域，每一个数据页中都包含多条行数据。注意看图中最上面和最下面的两条特殊的行记录Infimum和Supremum，这是两个虚拟的行记录。在没有其他用户数据的时候Infimum的下一条记录的指针指向Supremum，当有用户数据的时候，Infimum的下一条记录的指针指向当前页中最小的用户记录，当前页中最大的用户记录的下一条记录的指针指向Supremum，至此整个页内的所有行记录形成一个单向链表。
行记录被Page Directory逻辑的分成了多个块，块与块之间是有序的，也就是说“4”这个槽指向的数据块内最大的行记录的主键都要比“8”这个槽指向的数据块内最小的行记录的主键要小。但是块内部的行记录不一定有序。
每个行记录的都有一个n_owned的区域（图中粉红色区域），n_owned标识这个这个块有多少条数据，伪记录Infimum的n_owned值总是1，记录Supremum的n_owned的取值范围为[1,8]，其他用户记录n_owned的取值范围[4,8]，并且只有每个块中最大的那条记录的n_owned才会有值，其他的用户记录的n_owned为0。
所以当我们要找主键为6的记录时，先通过二分法在稀疏索引中找到对应的槽，也就是Page Directory中“8”这个槽，“8”这个槽指向的是该数据块中最大的记录，而数据是单向链表结构所以无法逆向查找，所以需要找到上一个槽即“4”这个槽，然后通过“4”这个槽中最大的用户记录的指针沿着链表顺序查找到目标记录。
索引类型
- 聚集索引
数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。
- 非聚集索引
该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。普通索引，唯一索引，全文索引都是非聚集索引
前面关于数据存储的都是演示的聚集索引的实现，如果上面的用户表需要以“用户名字”建立一个非聚集索引，是怎么实现的呢？我们看下图：
非聚集索引的存储结构与前面是一样的，不同的是在叶子结点的数据部分存的不再是具体的数据，而数据的聚集索引的key。所以通过非聚集索引查找的过程是先找到该索引key对应的聚集索引的key，然后再拿聚集索引的key到主键索引树上查找对应的数据，这个过程称为回表！
innodb和myisam
innodb引擎数据在物理上是按主键顺序存放，而MyISAM引擎数据在物理上按插入的顺序存放