专栏首页爱可生开源社区第15期:索引设计(索引组织方式 B+ 树)

第15期:索引设计(索引组织方式 B+ 树)

谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 IO。

任何有数据的场景几乎都有索引,比如手机通讯录、文件系统(ext4\xfs\ntfs)、数据库系统(MySQL\Oracle)。数据库系统和文件系统一般都采用 B+ 树来存储索引信息,B+ 树兼顾写和读的性能,最极端时检索复杂度为 O(logN),其中 N 指的是节点数量,logN 表示对磁盘 IO 扫描的总次数。

MySQL 支持的索引结构有四种:B+ 树,R 树,HASH,FULLTEXT。

本篇简单介绍下 B+ 树,下一篇讲 MySQL 常用的两种引擎 MyISAM 和 InnoDB 的 B+ 树索引实现,其余的后面会讲到。

一、什么是二叉树?

再讲什么是 B+ 树之前,先来了看下什么是二叉树。

树本身是一种数据存储结构,因为类似现实生活中的树而命名。

一个看似没有修剪过的树,其实这是一棵二叉树,每个节点最多有两个子节点

树相关的基础概念:

拿图 1 这棵树举例说明:

  • 根节点:6 为根节点,根节点没有父节点,有儿子节点,一般叫做 ROOT 节点;
  • 儿子节点:8 和 4 是 6 的儿子节点,4 是左儿子,8 是右儿子;
  • 父节点:6 是 4 和 8 的父节点,父节点是儿子节点的上层节点;
  • 叶子节点:4 和 5 是叶子节点,叶子节点指的是除根节点外没有儿子的节点;
  • 兄弟节点:8 和 4 互为兄弟节点,因为有共同的父亲 6。10,9,7 三个节点没有兄弟,都只有一个儿子;
  • 层数:一棵树的节点层数。图 1 层数为 6;
  • 高度:自下向上遍历,从叶子节点遍历到根节点所需要的节点数量。叶子节点 5 到根节点遍历 7,9,10,8,6,这棵树的高度为 5;
  • 深度:自上而下遍历,从根节点到叶子节点遍历所需要的节点数量,同样,这棵树的深度也是 5;
  • 高度和深度一般以 0 开始计算,当然也有按照从 1 开始计算的;
  • 平衡因子:某节点的左子树与右子树深度的差值,一般结果为绝对值。 如果任何一个子树不存在,按照 0 处理。比如节点 10 的平衡因子就是 3;

图 1 是一颗非常普通的树,非常容易退化为一张链表。如果把图 1 换成如下图, 根节点就变为 4,6 退化为 4 的儿子节点,这棵树就退化为一张链表。

链表的查找非常慢,只能按照节点顺序查找,每个节点都遍历一遍,时间复杂度为 O(n),无法随机查找。

二、平衡二叉树(AVL)

那对图 1 进行下改造,把数据重新节点重新连接下,图 2 如下:

图 2 可以看到以下特性:

1. 所有左子树的节点都小于其对应的父节点(4,5,6)<(7);(4)<(5);(8)< (9);

2. 所有右子树上的节点都大于其对应的父节点(8,9,10)>(7);(6)>(5);(10)>(9);

3. 每个节点的平衡因子差值绝对值 <=1;

4. 每个节点都符合以上三个特征。

满足这样条件的树叫平衡二叉树(AVL)树。

问:那再次查找节点 5,需要遍历多少次呢?

由于数据是按照顺序组织的,那查找起来非常快,从上往下找:7-5,只需要在左子树上查找,也就是遍历 2 次就找到了 5。假设要找到叶子节点 10,只需要在右子树上查找,那也最多需要 3 次,7-9-10。也就说 AVL 树在查找方面性能很好,最坏的情况是找到一个节点需要消耗的次数也就是树的层数, 复杂度为 O(logN)

如果节点非常多呢?假设现在有 31 个节点,用 AVL 树表示如图 3:

图 3 是一棵高度为 4 的 AVL 树,有 5 层共 31 个节点,橙色是 ROOT 节点,蓝色是叶子节点。对 AVL 树的查找来看起来已经很完美了,能不能再优化下?比如,能否把这个节点里存放的 KEY 增加?能否减少树的总层数?那减少纵深只能从横向来想办法,这时候可以考虑用多叉树。

三、B 树

B 树是一种多叉的 AVL 树。B-Tree 减少了 AVL 数的高度,增加了每个节点的 KEY 数量。

B 树的特性:(m 为阶数:结点的孩子个数最大值)

1. 树中每个节点最多含有 m 个孩子节点 (m>=2);

2. 除根节点和叶子结点外,其他节点的孩子数量 >=ceil(m / 2);

3. 若根节点不是叶子结点,最少有两个孩子

  • 特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点;

4. 每个非叶子结点中包含有 n 个关键字信息:(n,P0,K1,P1,K2,P2,......,Kn,Pn) 其中:

  • Ki (i=1...n) 为关键字,且关键字按顺序升序排序 K(i-1)< Ki
  • Pi 为指向儿子节点的指针,且指针 P(i-1) 指向的儿子节点里所有关键字均小于 Ki,但都大于 K(i-1)
  • 关键字的个数 n 必须满足:[ceil(m / 2)-1]<= n <= m-1
  • 如果一个结点有 n 个关键字,那么该结点有 n+1 个分支。这 n+1 个关键字按照递增顺序排列
  • 所有叶子结点都出现在同一层,是所有遍历的终点位置

按照这个要求,把图 3 简单变为一棵 B 树,见图 4:

图 4 是一棵 4 阶 B 树,总共有 11 个节点,节点数比图 3 少了 20 个;层数为 3,比图 3 少了两层。实际应用中,每个最小单元不是 KEY,而一般是按照块(BLOCK)来算。比如磁盘文件系统 EXT4 每块 4KB;数据库比如 PostgreSQL 是 8KB,MySQL InnoDB 是 16KB, MySQL NDB 是 32KB 等。

所以再次理清图 4 的 B 树,变为图 5:

图 5 每个节点的基本单元是一个磁盘块(BLOCK,默认 4KB),根节点含有一个键值,其他节点含有 3 个键值,每个磁盘块包含对应的键值与数据。

比如现在要读取 KEY 为 31 的记录:先找到根节点磁盘块(1),读入内存。(第一次 IO);关键字 31 大于区间(16,),根据指针 P2 找到磁盘块 3,读入内存(第二次 IO);31 大于区间(20,24,28),根据指针 P4 读取磁盘块 11(第三次 IO),在磁盘块 11 中找到 KEY 为 31 的记录,返回结果。这期间有三次磁盘 IO 的读取。可以明确看到,B 树相对于 AVL 树,减少了树的节点数与树的深度,减少了磁盘 IO。

看到这里其实有一个问题,三次 IO,前两次 IO 其实从磁盘读取了不必要的数据,因为只用比较 KEY,所以非叶子节点对应的 DATA 完全没有必要,如果 DATA 很大,那完全是浪费内存资源。考虑下能否把非叶子节点的 DATA 拿掉?

四、B+ 树

B+ 树是对 B 树的一个小升级。大部分数据库的索引都是基于 B+ 树存储的。MySQL 的 MyISAM 和 InnoDB 引擎的索引都是基于 B+ 树存储。

B+ 树最大的几个特点:

1. 非叶子节点只保留 KEY,放弃 DATA;

2. KEY 和 DATA一起,在叶子节点,并且保存为一个有序链表(正序,反序,或者双向);

3. B+ 树的查找与 B 树不同,当某个结点的 KEY 与所查的 KEY 相等时,并不停止查找,而是沿着这个 KEY 左边的指针向下,一直查到该关键字所在的叶子结点为止。

那对图 5 的 B 树做一个调整,变为以下 B+ 树,见图 6:

图 6 是一棵 6 阶 B+ 树。不同于图 5,非叶子节点不再包含除了主键外的数据,数据全部放在叶子节点,并且所有叶子节点存放在一个单向链表里,当然也可以双向链表。可以看到,B+ 树同时具有平衡多叉树和链表的优点,即可兼顾 B 树对范围查找的高效,又可兼顾链表随机写入的高效, 这也是大部分数据库都用 B+ 树来存储索引的原因。

本篇是为了下一篇介绍 MySQL 的两种常用引擎:MyISAM 和 InnoDB 索引结构做了一个铺垫,下期见。

本文分享自微信公众号 - 爱可生开源社区(ActiontechOSS),作者:杨涛涛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 第23问:3 节点 MGR 集群,能不能将一个节点放在地球另一端?

    我们都知道,MGR 用了类 Paxos 机制的协议,协商过程只要多数节点同意即可达成一致。

    爱可生开源社区
  • 第14问:在 MGR 集群里,一个节点异常退出后,会发生什么?

    在一个 MGR 集群里,一个节点异常退出后,MySQL 会如何进行调度?异常的节点什么时候会被踢出集群?

    爱可生开源社区
  • 第19问:MGR 架构,如果一个节点网络不稳,消息缓存会被撑满么?

    1. MySQL 版本为 8.0.21(随 8.0 的小版本升级,MGR 参数和行为变更频繁,需要特别注意版本号)。

    爱可生开源社区
  • ignite TCP发现原理

    节点顺序 - 每个节点的内部属性(对于TcpDiscoverySpi,它只是一个统一增加的数字)。

    lilihongjava
  • 《Redis设计与实现》读书笔记(二十八) ——Redis集群节点结构与槽分配

    《Redis设计与实现》读书笔记(二十八) ——Redis集群节点结构与槽分配 (原创内容,转载请注明来源,谢谢) 一、概述 redis集群是...

    用户1327360
  • 数据结构:树与二叉树

    一颗高度为h,并含有2^h-1个节点的二叉树称为满二叉树,即树中的每一层都含有最多的节点。

    HLee
  • 《Redis设计与实现》读书笔记(三十) ——Redis集群节点复制与故障转移

    《Redis设计与实现》读书笔记(三十) ——Redis集群节点复制与故障转移 (原创内容,转载请注明来源,谢谢) 1、概述 redis集群的...

    用户1327360
  • 红黑树算法

    前情提要 红黑树是AVL树里最流行的变种,有些资料甚至说自从红黑树出来以后,AVL树就被放到博物馆里了。红黑树是否真的有那么优秀,我们一看究竟。红黑树遵循以下...

    机器学习算法工程师
  • 多叉树 & B树 & B+树 & B*树

    二叉树虽然操作效率比较高,但是如果数据一多,就会有好多好多的节点,需要进行好多次的I/O操作,构建出来的二叉树就会很高很高,也会降低操作速度。

    贪挽懒月
  • 像管理 Pod 一样管理 Node | TKE 节点池全面上线

    晏子怡,腾讯云产品经理,目前负责TKE集群、网络及调度模块。 从 K8s 的声明式设计理念谈起 Pod 模板 K8s 最优雅精妙的一个设计理念在于声明式  A...

    腾讯云原生

扫码关注云+社区

领取腾讯云代金券