索引类型

哈希索引

hash表是以键值对存储数据的，通过对key做hash运算从而定位到直接的元素

1、检索效率高

2、不能使用范围查询；允许"=","IN"和"<=>"查询；不允许WHERE price > 100查询

3、不能避免表扫描；

4、为了减少hash碰撞，需要执行一个负载因子，也就是说需要空出一些空间，来减少hash冲突，所以当数据量很大时，会浪费较多的空间

二叉树

image.png

如果我们需要查找id=12的用户信息，利用我们创建的二叉查找树索引，只需要3次即可找到匹配的数据。如果在表中一条条的查找的话，我们需要6次才能找到。

平衡二叉树

1、左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值（平衡因子 ）不超过1。也就是说AVL树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度）

2、树的高度越高，查找速度越慢

B树索引

一个节点可以存储两个值，意味着它的树高度，比二叉树的高度更低，它的查询速度就更快

image.png

B+树

B+树一直比较特殊的B树，它只将数据存储在叶子节点上，同时每个叶子节点间还是指针相连

叶子节点中包含了key和value，key存储的是1-10这些数字，value存储的是数据存储地址，非叶子节点中只是包含了key，不包含value。

所有相邻的叶子节点包含非叶子节点，使用链表进行结合，有一定顺序排序，从而范围查询效率非常高

image.png