索引

概念

索引就好比书的目录，用于加快查找的效率，如果数据库中没有索引，此时查找的时候就需要把整个表遍历一遍

作用

1、索引就是为了避免数据库进行顺序查找，提高查找效率，但是会减慢插入、修改和删除效率（需要同步修改索引）
2、索引会占用额外的空间（用空间换时间）
3、给某列加索引时加在主键上的索引和其他列上的索引是不同的

主键索引叶子节点存储的就是数据的完整记录
其他索引叶子节点存的是主键id

应用场景

1、数据量较大，且经常对这些列进行查询
2、改数据库表的插入、修改和删除操作频率较低
3、有足够的磁盘空间

数据结构（B+树）

真实的索引的数据结构是一种N叉搜索树=》 B+树

B树

说起B+树，先从B树来看
B树，也就是B-树（就念B树）

B树和二叉树差异：
1、每个节点不是二叉而是n叉
2、每个节点可能存储多个数据
3、每个节点存的数据的个数和该节点的度是相关的，度=存的数据个数+1

1、所以在B树上查找就是N分查找，效率比二分快很多，
2、由于每个节点存储了多个数据，每个节点又有多个度，和二叉树相比，在保存相同个数元素时，B树的高度就会更低些。

B树的叶子和非叶子都是存储数据，都要放在磁盘上

B+树

和B树相比
1、每一层的元素之间都链接到一起
2、数据都在叶子节点上，非叶子节点上只保存了一些辅助查找的边界信息
3、B树的叶子和非叶子都是存储数据，都要放在磁盘上，但是B+树 叶子放到磁盘上，非叶子放到内存中，查找效率就更高了（减少了读磁盘的次数）

特点：

• 1、仍然是N叉树，层级小，非叶子节点不再存储数据，数据只存储在同一层的叶子节点上，B+树从根到每一个节点的路径长度一样，而B树不是这样== 

•  2、叶子之间，增加了链表(图中红色箭头指向)，获取所有节点，不再需要中序遍历，使用链表的next节点就可以快速访问到 

•  3、范围查找方面，当定位min与max之后，中间叶子节点，就是结果集，不用中序回溯（范围查询在SQL中用得很多，这是B+树比B树最大的优势） 

• 4、 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储 

• 5、非叶子节点，不存储实际记录，而只存储记录的KEY的话，那么在相同内存的情况下，B+树能够存储更多索引 

查询任何一条记录速度是比较平均的，不会出现效率差异大的情况，不需要进行额外的中序遍历，遍历链表就是得到中序结果，处理范围查找更高效。

为什么不用二叉搜索树

如果二叉树比较平衡查找效率为O（logN）
二叉搜索树，内部元素是有序的，中序遍历结果就是有序的

如果借助二叉搜索树实现查找id<6并且>3的学生信息
可以先找到中序遍历中id=3以及id=6，(按照二叉搜索树的典型方式查找也就是折半查找既可)
中序遍历 （中序遍历的效率是O（N）） 中3到6之间的就是要查找的结果。
相比于哈希表二叉搜索树虽然能够处理范围查找，但是处理效率低

为什么索引不用二叉搜素树：

1、二叉搜索树每个节点最多两个子节点，当数据量比较大的时候，树的高度就会比较高，这样中序遍历递归的次数也就会多，最终操作效率低。
2、二叉搜索树，直接获取中序遍历也不是很高效。O（N），如果是O（N），就跟顺序查找差不多了，甚至可能还会更慢。
3、二叉树每个节点只存储一个记录，一次查询在树上找的时候花费磁盘IO次数较多

为什么不用哈希表

哈希表的查找效率为O（1）

数据库的索引使用哈希表，只能解决一些匹配相等的情况但是无法解决比较范围的问题。
eg：查找id<6并且>3的学生信息
select * from student where id < 6 and id >3 ，哈希表是不能处理的。

哈希表只能处理相等的情况,像 > < <= >= between and这种是无法处理的；
因为哈希表查找是先把key通过哈希函数映射计算得到下标再根据下标取到对应的链表，再去遍历比较key是否相等****，所以如果想要判断大于等于就无法实现。

操作

查看索引

只要指定了primary key 就是主键索引，跟数据表中的自增无关

创建索引

删除索引

补充 explain