索引背后的数据结构B-Tree B+Tree

win_7_maplestory-001.jpg
为了面试GG

前言

探讨下,数据库背后的索引原理,深入明白为什么以下内容

  • B Tree 数据结构
  • 索引的原理
  • 存储引擎的 InnoDB与MyISAM区别
  • 最左原则的形成原因

B Tree 及其变形

B Tree又叫Balance Tree,多路平衡树(B - Tree就是B Tree),意为平衡树。主要用于文件系统的索引,这种数据结构有种变形的形态叫做B+ Tree,稍后会介绍。B Tree是Inodb、MyISAM支持的索引方法之一,也是主要用于生产的!

B Tree 的特点

如果你还不懂什么是B Tree,推荐看这位大佬的漫画理解,画的不错:漫画算法:什么是 B 树?,再来看它的特点

一棵树M度的 B Tree有如下:

  • 一个节点最多有M-1个KEY,M个孩子
  • 出根节点和叶子节点之外,每个节点至少有[ceil(M/2),M]个孩子
  • 关键字KEY的顺序是递增的

B-Tree

时间复杂度

为什么使用多路平衡树而不是用二叉树,难道是应为多路平衡式的时间复杂度要低吗?

平衡二叉树 : AVL树 O(logn)
多路平衡式树 : O(logn)+n*O(M)

O(logn) 不用解释了吧,n*O(M)是因为找儿子节点的时候,需要遍历当前节点。

既然,多路平衡树的时间复杂度要高,为什么还要选择它呢?这就要考虑IO了,我们无法将数据一次性的读到内存里。一次只能读一块,而读io的速度远远远远远远低于读内存的速度。如果我们把每个节点当做磁盘中的一块区域,如果用平衡二叉树,会非常高,就意味着要多次读写磁盘,而用多路平衡树,它很矮,意味着读写次数少,而遍历比较的n*O(M)时间,在内存里,所以基本可以忽略了。所以选择多路平衡树!

B+ Tree

主要到上面的问题没有 B Tree在每个节点都存储了Key,Data(数据库内容),和指针。而每一块磁盘区域是有限的,为了让磁盘存储更多的Key,树边的更矮。B+ Tree把Data去了,变成了如下结构

B+Tree

所以数据结构层面上是用一个东西。

存储效率计算

InnoDB存储引擎中页的大小为16KB,Int是4B,一个磁盘能存4K个主键。3层的话就是

4*4*4*10^3*10^3*10^3=16亿条数据=无敌

MySQL主要引擎背后的秘密

在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

MyISAM索引实现

可以看到MyISAM存储的DATA是指针,所以修改数据库内容,并不会修改索引,只是内存的内容变了。

非聚集索引

定义:该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同,一个表中可以拥有多个非聚集索引。

MyISAM使用的就是非聚集索引,索引存储的只是指针,磁盘物理存储的实际位置和存有没有关系。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

InnoDB索引实现

第二,与MyISAM不同的是,辅助索引用(非主键的索引)的是储存Data的是主键的值,而不是地址。所以,聚集索引以主键查询非常高效,辅助索引需要查询二次,第一次查出主键,第二次用主键查询结果。

InnoDB索引实现

聚集索引

定义:数据行的物理顺序与列值(一般是主键的那一列)的逻辑顺序相同,一个表中只能拥有一个聚集索引。

显然InnoDB是聚集索引,它主键位置就是BTree的Key,Data就是数据,整个索引就是数据库文件,必定是聚集索引!

最左匹配原则

利用数据结构理解最左匹配原则,我们知道了索引的底层是Btree,只不过联合索引在键值数量不止一个,而是多个。构建一颗BTree只能有一个键,因此构建BTree的时候就是用联合索引的最左字段

1281680-20190117145740508-758737271.png

此时不难发现

  1. 主键 a 1,1,2,2,3,3是有序的,b 是无须的 1,2,1,4,1,2。

  2. 当主键一样时,b是有序的

总结

  • 例如:a = 1 and b = 2当左边a确定时,b也是可以确定的。因为b是有序的此时。也就是最左匹配原则的=和in可以乱序,比如a = 1 and b = 2 建立(a,b)索引可以任意顺序,mysql的查询优化器会帮你优化成索引可以识别的形式
  • 例如: a>10andb=2此时左边a是不确定的,自然b就是无序的,a字段可以匹配上索引,但b值不可以,因为a的值是一个范围,在这个范围中b是无序的。索引失效。也就是,mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配

参考BLOG

坚持原创技术分享,您的支持将鼓励我继续创作!