索引

索引原理

定义：索引是数据库系统中的一个排序的数据结构，用于协助快速查询。

索引的算法：hash<搜索二叉树<平衡二叉树<btree<b+tree

数据库索引为什么要用b+树：

从数据结构来说，hash是比较常用的寻址算法，能够支撑快速查找，但是他只适合精确查找，范围查询则效率不高，同时hash存在hash碰撞问题，两个对象可能具有同一个hash值，比如16%24根40%24，值都是16，可以在hash中加入链表解决问题，但是效率就低了；

另外因为范围查询的问题因此二叉树优势会大点，二叉树主要是包括平衡二叉树以及红黑树，

红黑树的特征是会自动调整树的形态，使其保持基本平衡，但是普通的二叉查找树则会退化成链表，红黑树则会不断调整树的形态，因此可能会造成极端的情况发生；

平衡二叉树的特性是它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，因此它不会存在极端的情况，查询的性能比红黑树要高，但是写的速度会低一点；

看起来 AVL 树作为数据查找的数据结构确实很不错，但是 AVL 树并不适合做 Mysql 数据库的索引数据结构，因为考虑一下这个问题：

数据库查询数据的瓶颈在于磁盘 IO，如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=7 这个数据我们就要进行磁盘 IO 三次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。而IO次数取决于树的高度，因此要将瘦高树变成矮胖树

因此，针对这个特性引出了B树，B树一个节点存储的可以不只一个数据，内存增加了，但是它降低了IO的次数，从而提升了查询速度。B树是通过中序列遍历进行数据范围查询的，因为只要找到节点即可，所以查询并不稳定，理想情况下是在根节点，最坏情况是在叶子节点。b树主要用于文件系统以及部分数据库索引mongodb

而B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找

（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；

（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；

（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。

（4）非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

Innodb索引

为什么用b+树不用红黑树；红黑树根节点到叶子节点的最大的长度不能超过最小长度的两倍，一般放在内存使用，不太适合磁盘使用

b+索引存储的数据量的算法，一个page占16k，索引字段占用16bytes，那第一层就可以存储16kb/16bytes个节点，因为b+的子节点数与上级存储的节点一致，因此第二层可以存储1000*1000个节点

innodb引擎不能使用hash创建索引，hash主要是给memory引擎使用的

innodb索引与数据在同一个文件中，只有聚集索引的叶子节点存储的是整个行数据（如主键索引）

聚集索引

索引键值与物理行的存储顺序一致则为聚集索引，聚集索引最后会将整行数据存储到叶子节点上；

其他的为二级索引，二级索引存储了主键索引防止存储地址进行变化

没有主键索引，会使用第一个不包含空值的唯一索引 作为聚集索引

没有主键索引也没有唯一索引，会生成一个6个字节隐藏的**_rowid**作为聚集索引

回表：指二级索引查询到后会再次查询主键索引获取数据的过程

前缀索引

针对字段过长的列可以创建前缀索引，指定索引字段的长度 index column(‘name 6’)

myisam索引

myisam数据与索引文件是分开存储的

索引文件存储的是数据文件中的地址，

索引使用原理

组合索引：多个字段组合形成索引，以第一个字段为基础进行b+tree的排序；查询条件必须包含第一个字段，否则不会使用组合索引

覆盖索引：查询的返回字段包含全部索引的字段，这样不会进行回表操作，提升查询效率

索引条件下推：数据库处理查询是先通过存储引擎将索引列查询过滤后将未用到索引的数据返回给服务端二次过滤，如果返回的数据过多则会影响查询性能，因此mysql默认开启条件索引下推的功能，会在存储引擎中将数据处理后返回给服务端，提升服务端的处理效率