提高数据库的查询效率一种方式是创建索引, 索引是帮助Mysql高效获取数据的数据结构, 今天学习一下mysql数据库的索引的原理, 可以更好的使用索引, 提高数据库的查询效率
注意
索引需要占用磁盘空间，因此在创建索引时要考虑到磁盘空间是否足够
创建索引时需要对表加锁，因此实际操作中需要在业务空闲期间进行
优势：可以快速检索，减少I/O次数，加快检索速度；根据索引分组和排序，可以加快分组和排序；
劣势：索引本身也是表，因此会占用存储空间，一般来说，索引表占用的空间的数据表的1.5倍；索引表的维护和创建需要时间成本，这个成本随着数据量增大而增大；构建索引会降低数据表的修改操作（删除，添加，修改）的效率，因为在修改数据表的同时还需要修改索引表；
原理
1. 二分查找
二分查找又名拆半查找, 使用二分查找前提是数据必须是排好序的，查找数x时先从中间查找，如果x小于中间数则在对前半部分继续二分查找, 相反对后半部分进行二分查找,知道找到要查找的数x.
2. 二叉树
二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。
二叉树的特性:
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
**二叉树的查找速度和树的高度成反比 , 但是二叉树不稳定 ,当二叉查找树根节点的左右子树极度不平衡时，就退化成了链表 , **查找速度和高度成正比。
极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求。我们需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树，一种特殊的二叉查找树，平衡二叉查找树(红黑树)。平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。
3. 平衡二叉树(红黑树)
平衡二叉树有两大特性:
1). 左右子树深度之差的绝对值不大于1。
2). 左右子树都是平衡二叉树。
平衡二叉树如果出现不平衡 , 会自动调整 ,根据新插入节点和最低不平衡节点的位置进行调整 , 使树结构保持平衡。这样保证了树的深度 , 从而提高查找效率局号。
平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。
在平衡二叉树的基础上如何优化 , 从而提高查找效率 ?
4. 平衡多路查找树(B树)
每一个节点即存储数据 , 有存储相应的指针 。
往B树中依次插入 6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4动图演示如下:
对于一颗节点为N度为M的子树，查找和插入需要logM-1N ~ logM/2N次比较
B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速
磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分，寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右。
磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO ,我们只需要保证一个节点的查找在一页的范围内 , 也就是4K或者是8K , 这样读取一个节点的数据只需要一次IO。这样为了减少IO次数 , 存储的内容就是有限的 , 在此基础上如何再次优化 ,降低树的高度 , 提高查询效率呢 ?
5. B+树
B+树非叶子节点只存储指针 , 并不存储相应的数据 , 只有叶子结点存储数据 , 都是相连的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。非叶子节点只存储指针 , 在存储内容大小一定的情况下 , 可以存储更多的内容(指针) , 在数据一定时 B+树的高度可以更低 , 从而提高查询速度 , 并且由于所有数据全存储在叶子结点 , 因此每次查询的次数是一样的 。
演示地址: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
M=4 阶的B+树
依次插入 6 10 4 14 5 11 5 15 3 2 12 1 7 8 8 6 3 6 21 5 15
总结
相同思想和策略 从二叉树、平衡二叉树、B树、B+树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；
不同的方式的磁盘空间利用 不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；
mysql 采用的是B+树的结构
根据这些特性 , 可以看出建立索引的原则:
1、离散性 2、查询频率高、更新频率低 3、索引字段能小则小 4、大字段不适合建索引
