B+Tree索引为什么可以支持千万级别数据量的查找——讲讲mysql索引的底层数据结构

MySQL索引底层数据结构

索引是存储引擎快速找到记录的一种数据结构

一、 有索引与没索引的差距

先来看一张图:

左边是没有索引的情况,右边是作为col2字段 二叉树索引的情况。

假如执行查找(假设表为 t)

select *from t where col2 = 89;

那么,左边的情况,需要比较6次才能找到,右边的情况,只需要比较2次就可以找到。当数据量非常大时,要查找的数据又非常靠后,那么二叉树结构的查询优势将非常明显。

扩展:

在右边二叉树的结构中,每个节点都是 key-value 键值对的形式。

key:col2所在行在磁盘文件中的指针(比如 34 所在行,通过 0x07 这个指针就能找到是第1行)

value:就是col2的值;

二叉树的特点:

左子节点值 < 节点值;

右子节点值 > 节点值;

二、 二叉树索引存在的问题

虽然二叉树能提高查找速度,但不是最优的,存在很大的问题。

比如:

通过图,可以看出,二叉树出现单边增长时,二叉树变成了“链”,这样查找一个数的时候,速度并没有得到很大的优化。

三、 进一步优化,用红黑树

二叉树出现上述情况,显然不太好。那用红黑树怎样呢?

先来看红黑树的结构

但红黑树最大问题是高度问题。

假设现在数据量有100万,那么红黑树的高度大概为 100,0000 = 2^n, n大概为 20。

那么,至少要20次的磁盘IO,这样,性能将很受影响。如果数据量更大,IO次数更多,性能损耗更大。

所以,如果能降低IO次数,将是一个非常好的解决方案。

四、 Hash表

Hash是MySQL中支持的两种索引结构中的一种。

Hash的大致原理是:

  1. 事先将索引通过 hash算法后得到的hash值(即磁盘文件指针)存到hash表中。
  2. 在进行查询时,将索引通过hash算法,得到hash值,与hash表中的hash值比对。通过磁盘文件指针,只要一次磁盘IO就能找到要的值。

例如:

在第一个表中,要查找col=6的值。hash(6) 得到值,比对hash表,就能得到89。性能非常高。

Hash表存在的问题:

但是hash表索引存在问题,如果要查询 带范围的条件时,hash索引就歇菜了。

例如:

select *from t where col1>=6;

hash索引就无能为力了,工作中一般用BTree用的多。

五、 B-Tree

回到红黑树的问题,之所以不选中红黑树,最大的原因是没有解决高度问题。(尽管高度相对无索引或普通二叉树已经降低很多,但数据量大时,仍然要多次磁盘IO)

而BTree索引能很好解决高度问题。

B-Tree 是一种平衡的多路查找(又称排序)树,在文件系统中和数据库系统有所应用,主要用作文件的索引。其中的B就表示平衡(Balance)。

BTree 的特性:

为了描述BTree,首先定义一条数据记录为一个**二元组[key, data]**,key为记录的键值,对于不同数据记录,key是互不相同的;data为数据记录除以key外的数据。那么BTree是满足下列条件的数据结构:

  1. d 为大于1的一个正整数,称为BTree的度;
  2. h为一个正整数,称为BTree的高度;
  3. key和指针互相间隔,节点两端是指针;

  1. 一个节点中的key从左到右非递减排序

  2. 每个指针要么为null,要么指向另外一个节点;每个非叶子节点由 n-1 个key 和 n个指针组成,其中

    d <= n <= 2d;

  3. 每个叶子节点最少包含一个key和两个指针,最多包含 2d-1个key 和 2d个指针,叶节点的指针均为null

  1. 如图

总结:

我们可以稍微总结一下,BTree具有:

  • 叶节点具有相同的深度
  • 叶节点的指针为空
  • 节点的数据索引从左到右递增排列

但是BTree仍然存在一些问题,比如执行下面的语句,查找col1 > 20 的值

select *from t where col1 > 20;

那么不但需要叶子节点>20的值,也需要非叶子节点.........

评论

暂无评论