索引的适用场景以及索引的数据结构
1.为什么使用索引？
它避免全表扫描，将整张表的数据全部或分批次加载到内存当中。存储的最小单位是块或者是页来组成的，将整个块加载进来然后轮循去扫描，找到我们要的目标在然后返回。所以这样查找的速度是比较慢的，但是他在数据比较少时，比如只有几十行数据，全加载到内存后，查找的速度就比较快。
如果在数据量很大的表里情况下，全表扫描就不适用了，所以这个时候就要避免全表扫描的情况发生，因此数据库就要引入索引。
目的是：加快查询速度
2.什么样的信息能称为索引
主要是一些关键字段信息：：主键，唯一键等
适合创建索引：
- 在经常需要搜索的列上，可以加快搜索的速度。
- 在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构。
- 在经常用在连接的列上，这 些列主要是一些外键，可以加快连接的速度。
- 在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的。
- 在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间。
- 在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。
不适合创建索引：
- 对于那些在查询中很少使用或者参考的列不应该创建索引。这是因为，既然这些列很少使用到，因此有索引或者无索引，并不能提高查询速度。相反，由于增加了索引，反而降低了系统的维护速度和增大了空间需求。
- 对于那些只有很少数据值（唯一性差）的列也不应该增加索引。这是因为，由于这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。
- 对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为，这些列的数据量要么相当大，要么取值很少。
- 当修改性能远远大于检索性能时，不应该创建索引。这是因为，修改性能和检索性能是互相矛盾的。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。因此，当修改性能远远大于检索性能时，不应该创建索引。
3.索引的数据结构
1）生成索引：建立二叉树进行二分查找
二叉树: 是每个节点最多只有两个子树的节点，左边的叫左子树，右边的叫右子树。左子树的值均比当前节点的值大，同时右子树的值比当前节点大。
注意：索引的存储块，与数据库的最小存储单位块或者是页并是一一对应的。每个索引的块指向的是关键字和指向索引的指针
平衡二叉树：又被称为AVL树。它是一颗空树或者他的左右两个子树的的高度差不超过1，且左右子树都是一颗平衡二叉树
优点：二叉树的查找采用的是二分查找，因为是对半查找他的效率是比较高的。时间复杂度为O(logn)
缺点：因为数据库的数据有可能会进行进行增加或者删除，此时就会发生一种情况，它可能会变成一颗线性的二叉树，这种情况下他的时间复杂度就变为O(n)，检所检率就大大降低了
如果对树进行旋转特性保持其是平衡二叉树，这样他的时间复杂度就维持O(logn)，岁间解决了查找速度的问题，但是他会有第二个问题，因为程序运行速度的瓶颈在IO，假设这些索引都在磁盘中，先发生一次IO将数据读入到内存当中，然后再次发生一次IO将7读入内存，再发生一次IO将6读入，也就是深度每增加一，就会发生一次IO。
总结：不管是二叉树，红黑树等，因为二叉树的孩子节点只有两个，而数据比较多，所以为了把数据组织起来，树的层次会很深，IO的次数也会多，这样检索的性能就会比全表扫描就会降低很多，此时它是无法满足优化查询的需求的。
所以优化查询的目的就是即降低优化查询的次数，又降低IO的次数，那就是把树变得矮一些，每个节点能存储的数多一些，由此就可以联系到B-Tree。
2）生成索引，建立B-Tree结构进行索引
B-Tree树的结构：
1.根节点至少包括两个孩子
2.树中每个节点最多有M个孩子(M>=2)
3.除根节点和叶节点外，其他每个节点至少有ceil(m/2) 个孩子
4.所有叶子结点都位于同一层
5.假设诶个非终端节点中包含n个关键字信息，其中
- Ki （i=1.....n）为关键字，且关键字升序排序 k(i-1) <ki
- 关键字的个数n必须满足：[ceil(m/2) -1]<=n<m-1
- 非叶子节点的指针：p[1],p[2]....p[M],其中p[1]指向关键字小于k[1]的子树，P[M]指向关键字大于k[M-1]的子树，其他p[i]指向挂念自属性（k[i-1],k[i]）的子树
B树的查找小路是O(n)
3）生成索引，建立B+Tree结构进行索引
B+树是B树的遍历，定义基本与B树相同除了：
1.非叶子节点的子树指针与关键字个数相同：表示了B+树可以存储和更多的关键字
4）生成 索引，建立Hash结构进行索引
4.密集索引和稀疏索引