简说 Mysql 索引原理

在互联网项目中,大部分都是读大于写的频率,这个比例一般在 10:1 。读的次数如此频繁,导致 IO 压力很大,如果说我们能够把查询的 IO 次数控制在常量级,那么这对数据库的性能提升是非常明显的,因此基于 B+ Tree 的索引结构出现了。

B+ Tree 的数据结构

如上图所示是 B+ Tree 的数据结构。由一个个的磁盘块组成的树形结构,每个磁盘存储着各种数据和指针。

注意:所有的数据都是存放在叶子节点上,非叶子节点不存放数据。

B+ Tree 是如何查找数据的呢?

以上图中的磁盘 1 为例,指针 P1 表示小于 17 的磁盘块, P2 表示在 17 ~ 35 之间的磁盘块,P3 则表示大于 35 的磁盘块。

假设我们要查找数据项 99,那么我们会先将磁盘 1 加载到内存中,此时发生一次 IO. 接着通过二分查找发现 99 大于 35,所以找到了 P3 指针。通过 P3 指针发生第二次 IO 将磁盘块 4 加载到内存。再通过二分查找发现大于 87,通过 P3 指针发生了第三次 IO 将磁盘块 11 加载到内存。最后再通过一次二分查找找到了数据项 99。

由此可见,如果一个几百万的数据查询只需要进行三次 IO 即可找到数据,那么整个效率将是非常高的。

观察树的结构,发现查询需要经历几次 IO 是由树的高度来决定的,而树的高度又由磁盘块,数据项的大小决定的。

磁盘块越大,数据项越小那么树的高度就越低。这也就是为什么索引字段要尽可能小的原因。