1. 索引的目的：

   ---

   索引好比书的目录，是为了加快查找的效率，如果数据库没有索引，需要把整个表遍历一遍如果针对顺序表查找，顺序表在内存中，内存的访问速度快，并且数据也没那么多，速度也还行，但是针对数据库表顺序查找，数据库的数据是在磁盘上，磁盘的访问速度更慢，并且数据量很多，处理速度会更慢。索引就是为了避免数据库进行顺序查找，提高查找效率

2. 索引可以考虑的数据结构

   ---

   ①哈希表

        缺点：只能处理相等的情况，不能处理其他逻辑。比如查找id<6并且id》3的学生信息

        ②二叉树

        优点：能处理范围查找(二叉搜索树内部是有序的，可以按照二叉搜索树的典型搜索方式)

        缺点：

      二叉搜索树每个节点两个叉，当数据量比较大的时候，树的高度就会很高，最终的效率也会很低

       二叉搜索树直接获取到中序遍历也不是很高效

        ③B+树（真实的索引结构)

        首先看一下B树

和二叉树的差异：

1. 每个节点不是二叉了，而实N叉
2. 每个节点不是存储一个数据了，而是存多个数据

     存的数据的个数+1=节点的度

优点：

1. 就是一个N分查找，效率比二分还高
2. 每个节点存放了多个数据，每个节点又有多个度，和二叉树相比，在保存相同个数的元素时，B树的高度会比二叉树低很多
3. 范围查找更容易

     B+树

和B树相比的变化

1. 每一层的叶子都连接到一起了
2. 数据只存在叶子节点上，非叶子节点只保存一些辅助查找的边界信息

数据：保存的数据库表中的一行

非叶子节点只保存了id，辅助想要找到想要的id  对应的节点

优点：

1.查询任何一条记录的速度都是比较平均的，不会出现效率差异大的情况

2.不需要进行额外的中序遍历了，遍历链表就是得到中序结果，范围查找效率更高

3.叶子放到磁盘上，非叶子放到内存中，查找效率更高（减少读取磁盘的次数）

4.索引在内存中占用的实际开销也不高

5.非叶子的查找是在内存中，叶子的查找在磁盘上

缺点：

加快查找效率，减慢出入删除修改效率（因为要同步修改索引结构）

索引也会占用额外空间（使用空间来换时间）