数据库系列 | MySQL索引数据结构算法

1索引数据结构

索引是帮助MySQL高效获取数据的排好序的数据结构（容易忽略的点：排好序）

上图中有一张表，表名为 t ，表中有7条数据；使用 select * from t where t.clo2 = 89 查询；

若表中没有创建索引，则会全表扫描，一条一条的遍历查询，需要遍历 6 次，查询一行数据至少和磁盘做一次I/O操作（I/O是很耗性能的），至少要做 6 次 I/O 操作；

2索引数据结构

1. 二叉树
2. 红黑树
3. Hash表
4. B-Tree

1. 二叉树

语法：左边的子元素小于父元素，右边的子元素大于父元素。

字段 Col1 按照自增

如果数据是单边增长的情况 那么出现的就是和链表一样的数据结构了，树高度大。

这样查询 4 次就找到数据了；

当然，在极端情况下，若按照大小顺序插入二叉树，则会形成单边增长的二叉树，这样使用索引的时候和全表扫描是一样的了；

2. 红黑树

语法：当单边的节点大于3时候，就会自动调整，这样可以解决二叉树的弊端；红黑树也叫平衡二叉树；

同样我们查找6，在二叉树中我们需要经过6个节点才能找到（1-2-3-4-5-6）,红黑树中我们只需要3个节点（2-4-6），但是mysql索引的数据结构并不是红黑树，因为如果数据量大了之后，树的高度就会很大。

当然，红黑树也有弊端的，当数据量特别大的时候，红黑树的高度特别大；假如有500W条数据，则红黑树高度为 23，若我们要查找的刚好是红黑树的叶子节点，则需要查找 23 次才可以，即要发生 23 次的磁盘 I/O 操作，性能就太差了；

3. Hash表

若索引使用的Hash存储的，存储的时候先做一次hash运算，根据 hash 的值就可以快速的定位数据的磁盘指针，这样就不管表里面有多少数据，我们的查询效率都非常的快；

在实际中为什么使用 B-Tree 或 B+Tree 来存储索引的方式更多，而不太使用 hash 呢？

• 原因1：若使用 select * from t where clo2 > 6，这种查找范围的SQL，那Hash就不能搞定了，就不会走索引了；而且对排序hash也没有办法；
• 原因2：hash会产生 hash 碰撞，MySQL的底层对hash做了处理，很少会发生hash碰撞的；

4. B-Tree

语法：叶子节点具有相同的深度，叶节点的指针为空；所有索引元素不重复；一个节点可以存储多个元素，节点中的数据索引从左到右递增排列

若 Max. Degree = 4，则如下图所示：

这样只查询 2 次就找到了；当然 B-Tree 也是有弊端的；以下是 B-Tree 的存储，数字为key，data为对应的数据；若一个节点我们申请的空间为16KB，若data中的数据过大，则一个节点能放的数据量越小，这样就会造成树的高度比较大了（比红黑树高度小点）；