MySQL索引优化底层原理

慢查询如何优化？
一条sql一般执行几到几十毫秒，但是在千万级别的数据表面前，查询很慢，几秒或者甚至几十秒，我们一般通过索引优化查询，那为什么索引就可以解决慢查询的问题，为什么加上索引就能在千万级别的索引中就能查询到？我们不能把开发停留在浅层次，要知其然，并知其所以然

索引的本质

索引是帮助MySQL高效获取数据的排好序的数据结构

索引数据结构

• 二叉树
• 红黑树
• hash表
• B-Tree

首先，我们要明确，MySQL底层用的B树，或是B+树的数据结构，而不是二叉树，也就是说二叉树在查找过程中存在明显弊端。例如：

在这样一张表中，他用二叉树是如何存储的

可以看到，二叉树变成了类似链表的数据结构，但是他依然是个二叉树，只是左边没有元素，我们知道二叉排序树中节点的左子节点<节点<右子节点，如果我们在这样的二叉树里，要找到8这个元素，需要从上到下依次找8次，可见二叉排序树的查找方式，在某些极端条件下，并不高效
如果我们用红黑树存储

可以看到，如果再次查找8这个元素，只需要依次查找4次，但是依然无法满足MySQL索引的高效查找要求，因为如果你用红黑树存储上百万条数据，那么树的高度也会相应很大，刚好数据又在叶子节点上怎么办？从树根一直到叶子节点依次查找？
也就是说问题出在树的高度上，数据量越大，树的高度越大，查找效率就越低，如果我们能控制树的高度，是不是查找效率就会很高了？
也就是B树，我们限制树的纵向高度，就在每个节点上横向发展

可以看到，在红黑树里，查找8这个元素需要4次，而B+树查找20这个元素只需要3次，只载入必需的节点到内存，尽可能减少磁盘I/O操作，非必需的存到外存。其实每次查找也会在节点上比较，但是节点里的数据会放在内存里，我们知道内存查找是很高效的。所以从表面上看，只进行了3次磁盘io查找
B+树和只是B树的一个变形，原理上是差不多的，只是他把所有的数据data值存放在根节点上，通过指针域的方式查找。