• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【Btree和 B+Tree】

admin

11月 28, 2021

BTree意思是多路平衡查找树,它是一种数据结构。MySQL的InnoDB和MyISAM存储引擎,都是使用它来存储索引。BTree可细分为B-Tree和B+Tree,B+Tree是B-Tree的升级版。MySQL的InnoDB和MyISAM存储引擎使用的是B+Tree。

B-Tree

为了描述B-Tree,首先定义一条记录为一个二元组[key, data] ,key为记录的键值,对应表中的主键值,data为一行记录中除主键外的数据。对于不同的记录,key值互不相同。如下图中的紫色部分就是key,橙色部分就是一行数据,绿色部分就是指针。

「系统架构」为什么使用索引就能提升查询效率,原来与BTree有关

一棵m阶的B-Tree有如下特性:

  1. 每个节点最多有m个子节点。 如上图所示是一个3阶的树,那最多有3个子节点。
  2. 除了根节点和叶子节点外,其它每个节点至少有ceil(m/2)个子节点。如上图所示是一个3阶的树,那每个节点至少有2个子节点。
  3. 所有叶子节点都在同一层,且不包含其它关键字信息
  4. 每个非终端节点包含n个关键字信息(P0,P1,…Pn, k1,…kn) ,关键字的个数n满足:ceil(m/2)-1 <= n <= m-1
  5. ki(i=1,…n)为关键字,且关键字升序排序。
  6. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki,但都大于k(i-1)
  7. 指针存储的是子节点所在磁盘块的地址

假设以根节点为例,关键字为17和35,P1指针指向的子树的数据范围为小于17,P2指针指向的子树的数据范围为17~35,P3指针指向的子树的数据范围为大于35。

当我们要查找关键字29时:

  1. 根据根节点找到磁盘块1,读入内存。【磁盘I/O操作第1次】
  2. 比较关键字29在区间(17,35),找到磁盘块1的指针P2。
  3. 根据P2指针找到磁盘块3,读入内存。【磁盘I/O操作第2次】
  4. 比较关键字29在区间(26,30),找到磁盘块3的指针P2。
  5. 根据P2指针找到磁盘块8,读入内存。【磁盘I/O操作第3次】
  6. 在磁盘块8中的关键字列表中找到关键字29。

分析上面过程,发现需要3次磁盘I/O操作,和3次内存查找操作。由于内存中的关键字是一个有序表结构,可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数,使每次磁盘I/O取到内存的数据都发挥了作用,从而提高了查询效率。

B+Tree

从上一节中的B-Tree结构图中可以看到,每个节点中不仅包含数据的key值,还有data值。而每一个页的存储空间是有限的,一般为16K(也可以调整),如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小。当存储的数据量很大时同样会导致B-Tree的深度较大,增大查询时的磁盘I/O次数,进而影响查询效率。

为解决这个问题,在B-Tree基础上就产生了一种新的数据结构B+Tree。

「系统架构」为什么使用索引就能提升查询效率,原来与BTree有关

一棵m阶的B+Tree的特性和m阶的B-Tree基本相同,除了以下几点:

  1. 非叶子节点上只存储key值信息,而不存储data信息
  2. 非叶子节点的子树指针与关键字个数相同
  3. 非叶子节点的子树指针 P[i] , 指向关键字值属于 [K[i], K[i+1]) 的子树( B- 树是开区间)
  4. 所有关键字都会出现在叶子节点的链表中(稠密索引),且链表中的关键字恰好是有序的。如上图所示的升序。

虽然,MySQL的InnoDB和MyISAM存储引擎使用的都是B+Tree结构,但是它们也有不同之处:

  1. InnoDB的B+Tree索引分为聚簇索引和非聚簇索引,而MyISAM的B+Tree索引都是非聚簇索引。
  2. InnoDB的主键索引为聚簇索引,辅助索引为非聚簇索引。主键索引的叶子节点保存了完整的记录,辅助索引的叶子节点并不包含行记录的全部数据,它除了包含键值外,还包含了相应行数据的聚簇索引键。
  3. MyISAM的非聚簇索引结构都是一样的,它的叶子节点保存的都是磁盘地址,真正的数据存储在另外的地方。

数据库索引的数据结构有很多种,比如:哈希索引、平衡二叉树索引、B树索引、B+树索引等等。

目前最流行的是B+树索引,那大家有没有想过为什么是B+树索引最流行,为什么其他索引应用不广泛。

就像为什么别人能拿2-3万的工资,我却只能拿一万的工资,大家有思考过吗?

哈希索引

hash大家应该非常的熟悉,就是我们老生常谈的HashMap里用到的技术。Hash索引其检索效率非常高,索引的检索可以一次定位。

可能很多人又有疑问了,既然Hash索引的效率这么高,为什么都用Hash索引而还要使用B-Tree索引呢?

任何事物都是有两面性的,Hash索引也一样,虽然Hash索引效率高,但是Hash索引本身由于其特殊性也带来了很多限制和弊端,主要有以下这些:

原因一:

Hash索引不能使用范围查询

Hash索引仅仅能满足”=”,”IN”和”<=>”查询(注意<>和<=>是不同的操作),不能使用范围查询,例如WHERE price > 100。

由于Hash索引比较的是进行Hash运算之后的Hash值,所以它只能用于等值的过滤,不能用于基于范围的过滤。

原因二:

Hash索引不能利用部分索引键查询。

对于复合索引,Hash索引在计算Hash值的时候,是组合索引键合并后再一起计算Hash值,而不是单独计算Hash值。

所以通过复合索引的前面一个或几个索引键进行查询的时候,Hash索引也无法被利用。

原因三:

Hash索引在任何时候都不能避免表扫描。

Hash索引是将索引键通过Hash运算之后,将 Hash运算结果的Hash值和所对应的行指针信息存放于一个Hash表中。

由于不同索引键存在相同Hash值,所以无法从Hash索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。

hash索引out出局

平衡二叉树索引

 

 

又称 AVL树。 它除了具备二叉查找树的基本特征之外,还具有一个非常重要的特点:它的左子树和右子树都是平衡二叉树。

且左子树和右子树的深度之差的绝对值(平衡因子 )不超过1。也就是说AVL树每个节点的平衡因子只可能是-1、0和1(左子树高度减去右子树高度)。

被淘汰的原因

  • 树的高度过高,高度越高,查找速度越慢
  • 他支持范围查找,但是他需要在进行回旋查找

比如我要找到大于5的数据

第一步我先定位到5,然后在树上按照二叉树规则去回旋查找大于5其他数据6、7、8、9、10。。。

如果大于5的数据很多,那速度是很慢的。

B树索引

 

 

大家可以看到B树和二叉树最大的区别在于:它一个节点可以存储两个值,这就意味着它的树高度,比二叉树的高度更低,它的查询速度就更快。这是他的优点

那为什么最终还是不用它呢,还是因为他在范围查找的时候,存在回旋查询的问题。同样order by排序的时候效率也很低,因为要把树上的数据手动排序一遍。

终极大佬:B+树

 

 

它是B数的升级版,B+树相比B树,新增叶子节点与非叶子节点关系。

叶子节点中包含了key和value,key存储的是1-10这些数字,value存储的是数据存储地址,非叶子节点中只是包含了key,不包含value。

所有相邻的叶子节点包含非叶子节点,使用链表进行结合,有一定顺序排序,从而范围查询效率非常高。

比如我们要查找大于5的数据:

  • 首先我们定位到5的位置
  • 然后直接将5后面的数据全部拿出来即可,因为这是有序链表,已经排好序了

我们在order by排序的时候为什么要使用索引进行排序,原因就在这。

如果大家还没懂,请留言给我吧

发表回复

您的电子邮箱地址不会被公开。