四时宝库

程序员的知识宝库

mysql索引数据结构(mysql中索引的数据结构)

MySQL索引使用的数据结构主要有BTree索引hash索引

对于hash索引来说,底层的数据结构就是哈希表,因此在绝大多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快;其余大部分场景建议选择BTree索引。

Hash表

Hash表我们都很熟悉,在Java中的HashMap,TreeMap就是Hash表结构,以键值对的形式存储数据。我们使用hash表存储表数据结构,Key可以存储索引列,Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高,时间复杂度为O(1);但是不支持范围快速查找,范围查找时只能通过扫描全表的方式,筛选出符合条件的数据。

显然这种方式,不适合我们经常需要查找和范围查找的数据库索引使用。

二叉树



上面这个图就是我们常说的二叉树:每个节点最多有两个分叉节点,左子树和右子树数据按顺序左小右大。

二叉树的特点就是为了保证每次查找都可以进行折半查找,从而减少IO次数。

但是二叉树不是一直保持二叉平衡,因为二叉树很考验根节点的取值,因为很容易在某个节点下不分叉了,这样的话二叉树就不平衡了(树倾斜),也就没有了所谓的能进行折半查找了,如下图:



造成原因:

因为左右子树深度差太大,这棵树的左子树根本没有节点--也就是它不够平衡。

所以,我们有没有左右子树深度相差不是那么大,更加平衡的树呢?

这个就是平衡二叉树,叫做 Balanced binary search trees,或者 AVL

平衡二叉树

平衡二叉树的定义: 左右子树深度差绝对值不能超过1。说白了就是,当左子树的深度是 2,右子树的深度只能是1或者3。

这个时候我们再按顺序插入数据,一定是这样,不会变成一棵“斜树”。



我们注意看:当我们插入了 数据 4 之后,如果按照二叉查找树的定义,3肯定是要在

2 的右边的,这个时候根节点1的右节点深度会变成2,但是左节点的深度是0,因为它

没有子节点,所以就会违反平衡二叉树的定义。

那应该怎么办呢?因为它是右节点下面接一个右节点,右-右型,所以这个时候我们

要把 2提上去,这个操作叫做左旋。


就上述平衡二叉树的特点来看,其实是我们理想的状态下,然而其实内部还是存在一些问题:

  • 时间复杂度和树的高度有关。树有多高就需要检索多少次,每个节点的读取,都对应一次磁盘的IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。磁盘每次寻道的时间为10ms,在数据量大时,查询性能会很差。
  • 平衡二叉树不支持范围查询快速查找,范围查询需要从根节点多次遍历,查询效率不高

B树:改造二叉树(多路平衡二叉树)

跟 AVL 树一样,B 树在枝节点和叶子节点存储键值、数据地址、节点引用。

它有一个特点:分又数(路数)永远比关键字数多1。比如我们画的这棵树,每个节

点存储两个关键字,那么就会有三个指针指向三个子节点(当然肯定不只存3个这么少)

MySQL的数据是存储在磁盘文件中的,查询处理数据时,需要先把磁盘中的数据加载到内存中,磁盘IO操作非常耗时,所以我们优化的重点就是尽量减少磁盘的IO操作。访问二叉树的每个节点都会发生一次IO,如果想要减少磁盘IO操作,就需要尽量降低树的高度。

那如何降低树的高度呢?

假如key为bigint=8字节,每个节点有两个指针,每个指针为4个字节,一个节点占用的空间为(8+4*2=16)。

因为在MySQL的InnoDB引擎的一次IO操作会读取一页的数据量(默认一页大小为16K),而二叉树一次IO操作的有效数据量只有16字节,空间利用率极低。为了最大化的利用一次IO操作空间,一个解决方法就是在一个节点处存储多个元素,在每个节点尽可能多的存储数据。每个节点可以存储1000个索引(16k/16=1000),这样就将二叉树改造成了多叉树,通过增加树的分叉树,将树的体型从高瘦变成了矮胖。构建1百万条数据,树的高度需要2层就可以(1000*1000=1百万),也就是说只需要两次磁盘IO操作就可以查询到数据,磁盘IO操作次数变少了,查询数据的效率整体也就提高了。

这种数据结构我们称之为B树,B树是一种多叉平衡查找树,如下图主要特点:

  • B树的节点中存储这多个元素,每个内节点有多个分叉。
  • 节点中的元素包含键值和数据,节点中的键值从大到小排列。也就是说,在所有的节点中都存储数据。
  • 父节点当中的元素不会出现在子节点中。
  • 所有的叶子节点都位于同一层,叶子节点具有相同的深度,叶子节点之间没有指针连接。


如果,在B树中查询数据的情况:

如我们要查询key等于10对应的数据data,根据上图我们可知在磁盘中的查询路径是:
						磁盘块1->磁盘块2->磁盘块6
  • 第一次磁盘IO:将磁盘块1加载到内存中,在内存中从头遍历比较,10<15,走左子树,到磁盘中寻址到磁盘块2。
  • 第二次磁盘IO:将磁盘块2加载到内存中,在内存中从头遍历比较,10>7,走右子树,到磁盘中寻址到磁盘块6。
  • 第三次磁盘IO:将磁盘块6加载到内存中,在内存中从头遍历比较,10=10,找到key=10的位置,取出对应的数据data,如果data存储的是行记录,直接取出数据,查询结束;如果data存储的是行磁盘地址,还需要根据磁盘地址到对应的磁盘中取出数据,查询结束。
相比较二叉平衡查找树,在整个查找过程中,虽然数据的比较次数并没有明显减少,但是对于磁盘IO
的次数会大大减少,同时,由于我们是在内存中进行的数据比较,所以比较数据所消耗的时间可以忽
略不计。B树的高度一般2至3层就能满足大部分的应用场景,所以使用B树构建索引可以很好的提
升查询的效率。


虽然看着查询很不错,但是其中还是存在可以优化的地方:

  • B树不支持范围查询的快速查找,例如:仍然根据上图,我们想要查询10到35之间的数据,查找到10之后,需要回到根节点重新遍历查找,需要从根节点进行多次遍历,查询效率有待提高。
  • 如果data存储的是行记录,行的大小随着列数的增加,所占空间会变大,这时一页中可存储的数据量就会减少,树相应就会变高,磁盘IO次数就会随之增加,有待优化。

B+树

B+树,作为B树的升级版,MySQL在B树的基础上继续进行改造,使用B+树构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题。

  • B树:叶子节点和非叶子节点都会存储数据。
  • B+树:只有叶子节点才会存储数据,非叶子节点只存储键值key;叶子节点之间使用双向指针连接,最底层的叶子节点形成了一个双向有序链表。


1.如果是等值查询:

假如我们查询值等于9的数据。查询路径磁盘块1->磁盘块2->磁盘块6。

  • 第一次磁盘IO:将磁盘块1加载到内存中,在内存中从头遍历比较,9<15,走左路,到磁盘寻址磁盘块2。
  • 第二次磁盘IO:将磁盘块2加载到内存中,在内存中从头遍历比较,7<9<12,到磁盘中寻址定位到磁盘块6。
  • 第三次磁盘IO:将磁盘块6加载到内存中,在内存中从头遍历比较,在第三个索引中找到9,取出data,如果data存储的行记录,取出data,查询结束。如果存储的是磁盘地址,还需要根据磁盘地址到磁盘中取出数据,查询终止。(这里需要区分的是在InnoDB中Data存储的为行数据,而MyIsam中存储的是磁盘地址。)


2.如果是范围查询:

假如我们想要查找9和26之间的数据,查找路径为:磁盘块1->磁盘块2->磁盘块6->磁盘块7

  • 前三次磁盘IO:首先查找到键值为9对应的数据(定位到磁盘块6),然后缓存大结果集中。这一步和前面等值查询流程一样,发生了三次磁盘IO。
  • 继续查询,查找到节点15之后,底层的所有叶子节点是一个有序列表,我们从磁盘块6中的键值9开始向后遍历筛选出所有符合条件的数据。
  • 第四次磁盘IO:根据磁盘块6的后继指针到磁盘中寻址定位到磁盘块7,将磁盘块7加载到内存中,在内存中从头遍历比较,9<25<26,9<26<=26,将数据data缓存到结果集中。
  • 逐渐具备唯一性(后面不会再有<=26的数据),不需要再向后查找,查询结束,将结果集返回给用户。


可以看到B+树可以保证等值和范围查询的快速查找,MySQL的索引就采用了B+树的数据结构。

总结一下,InnoDB 中的 B+Tree 特性带来的优势

  1. 它是BTree 的变种,B Tree 能解决的问题,它都能解决。B Tree 解决的两大问题是什么?(每个节点存储更多关键字;路数更多)
  2. 扫库、扫表能力更强(如果我们要对表进行全表扫描,只需要遍历叶子节点就可以了,不需要遍历整棵 B+Tree 拿到所有的数据)
  3. B+Tree 的磁盘读写能力相对于 BTree 来说更强(根节点和枝节点不保存数据区所以一个节点可以保存更多的关键字,一次磁盘加载的关键字更多)
  4. 排序能力更强(因为叶子节点上有下一个数据区的指针,数据形成了链表)
  5. 效率更加稳定(B+Tree 永远是在叶子节点拿到数据,所以 10 次数是稳定的)

例如: 假设一条记录是16bytes,一个叶子节点(一页)可以存储 10 条记录。非叶子节点可以存储多少个指针?

假设索引字段+指针大小为 16 字节。非叶子节点(一页)可以存储 1000 个这样的单元(键值+指针),代表有1000个指针。

树深度为2的时候,有1000^2个叶子节点,可以存储的数据为1000*1000*10=10000000(千万级别)

那么在查找数据时一次页的查找代表一次10,也就是说,一张千万级别的表,查询数据

最多需要访问 3 次磁盘。树的深度是怎么来的?根据你的键值类型和数据量计算出来的。字段值越大、数据量越大,深度越大。所以在 InnoDB 中 B+ 树深度一般为 1-3 层,它就能满足千万级的数据存储。

发表评论:

控制面板
您好,欢迎到访网站!
  查看权限
网站分类
最新留言
    友情链接