Mysql索引原理及各种tree的比较

索引是为了加速对表中的数据行的检索而创造的一种分散存储的数据结构

2、索引的实现

mysql的索引是由存储引擎来实现，不同的存储引擎实现方式不同。

3、存放位置

一般是存放在磁盘中

4、作用

• 减少扫描的数据行
• 可以把随机IO变成顺序IO
• 可以帮助我们在分组、 排序 等操作时，避免使用临时表

5、索引结构

我们都知道 mysql 的索引使用B树来实现的，那么为什么会考虑B树，不考虑其他数据结构呢？

5.1 首先我们来看普通的二叉树。

普通的二叉树不是绝对平衡的，会有一个问题，如下图：

它有可能会形成一个链表，这样就失去了二叉树的优势，需要遍历查找，性能查。

5.2 那么如果我们选择平衡二叉树呢？如下图：

平衡二叉树没有普通二叉树可能会形成链表的问题，但是它还有其他的问题。

a、它太深了

• 这里的太深是指树的高度，大家不要想歪了～
• 如果在数据量很大的情况下，这棵树的高度很可能成千上万，因此它的IO次数也会很频繁，会严重影响性能

b、它太小了

• 太小指的是每一个磁盘块（节点）保存的数据量太小了
• 没有利用好操作磁盘IO的数据交换特性（4K）
• 没有利用好磁盘IO的预读能力（空间局部性原理）

这里解释下为什么说没有利用好。

1、操作系统磁盘IO的数据交换一次默认是4KB大小，但是我们的节点里面存储的数据远远小于4KB，即我们进行了一次IO但是没有完全利用这次IO的数据交换大小，造成浪费。

2、操作系统磁盘IO具备预读能力，是什么意思呢？比如我们要读取一张20KB大小的jpg图片，我们第一次读了4KB的头内容，操作系统会认为我们可能需要接下来的16KB的剩余内容，所以会一次性把剩余的内容都传输给我们。

它有以下几个特点：