MySQL B-tree与B+tree索引数据结构剖析

2024-08-08 16:05:59

一、产生的背景

二叉查找树的查找时间复杂度是O(logN)，整体的查询效率已经足够高了，那么为什么还会有B树和B+树的进化演进呢? 主要的原因是：二叉树可能会退化成一个线性树，造成磁盘IO次数增高的问题，当有大量的数据存储的时候，二叉查找树查询不能将所有的数据加载到内存中，只能逐一加载磁盘页，每个磁盘对应树的节点，造成大量的磁盘IO操作（最坏的情况IO次数为树的高度），平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。所以，为了减少磁的IO的次数，必须降低树的深度，将瘦高的树变得矮胖。

1.1 进化要求

每个结点能存储多个元素
摒弃二叉树结构，采用多叉树

二、B-tree

B-Tree是一种多叉的平衡搜索树（并不一定是二叉的），以一个三阶B-tree为例子来分析，每个储存块都包含：关键字和指向孩子结点的指针，最多有M个孩子，M的大小主要取决于每个存储块的容量和数据库的配置，M表示M阶数的意思。

2.1 B-tree特性

根节点至少包括两个孩子，范围是[2,M]；
树中每个节点最多包含M阶数个孩子（M是阶数，3阶，即：每个节点最多包含3个孩子）；
除了根节点和叶子结点以外，其他每个节点至少有ceil(M/2)个孩子节点，ceil是取上限函数（M是阶数，3阶，即：每个节点至少有2个孩子）；
所有的叶子结点都位于同一层。

假设每个非叶子节点包含n个关键字信息，其中：

Ki(i=1,2..,n)为关键字，且关键字按顺序升序排序K(i-1)< Ki；
关键字的个数n必须满足：[ceil(m/2)-1]<=n<=m-1（非叶子结点的关键字 = 指向孩子的指针个数-1）；
非叶子结点的指针：P[1],P[2],...,P[M]；其中P[1]指向关键字小于K[1]的子树（即：3和5均小于8），P[M]指向关键字大于K[M-1]的子树（即：13和15均大于12），其他P[i]指向关键字属于(K[i-1],K[i])的子树，是开区间（即：9和10都处于8-12区间）；

假设需要查询数据15，查询步骤：

首先从根部开始找，15<17，往左边P1找，P1指向的子树关键字为8和12；
由于15比8和12都大，因此会找到P3；
P3指向了13和15，13<15，最终找到15；
查找的时间复杂度为O(logN)。

三、B+tree

3.1 B+tree特性

B+树是B树的变体，其定义基本上与B树相同，除了：

非叶子结点的子树指针与关键字的个数相同；
非叶子结点的子树指针P[i]，指向关键字值 [K[i],K[i+1])的子树，左闭右开区间；
非叶子结点仅用于索引，数据都保存在叶子结点中；
所有的叶子结点均有一个链指针指向下一个叶子结点；
B+树非叶子结点仅用来存放索引，能存储更多的关键字，使得B+树相对于B树来说更矮壮，能存储更多数据。
所有的数据都存储在叶子结点。

四、结论

B+tree相比B-tree更适合用来存储索引，原因如下：

B+树的磁盘读写代价更低，B+树内部节点不存放数据，只存放索引信息，因此其内部节点相对B-tree会更小，所以同一个盘快就能存储更多的关键字，一次性读入内存中需要查找的关键字也就越多，因此IO次数也就越低。
B+树的查询效率更加稳定，由于B+树内部节点并不是指向文件内容的节点，而只是叶子节点关键字的索引，索引任何一个数据的查询都必须是：任何关键字查询都是从根节点到叶子节点的查询路线，因此每个数据的查询效率都是稳定一致的。
B+树跟有利于对数据的扫描，B-tree在解决磁盘IO性能同时并没有解决元素遍历效率低下问题，而B+树只需要遍历叶子节点就可以实现对所有关键字的扫描，所有对数据库频繁的范围查询是有着更高的查询性能。

到此这篇关于MySQL B-tree与B+tree索引数据结构剖析的文章就介绍到这了,更多相关MySQL B-tree与B+tree内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

MySQL使用B+Tree当索引的优势有哪些

数据库为什么需要索引呢? 我们都是知道数据库的数据都是存储在磁盘上的,当我们程序启动起来的时候,就相当于一个进程运行在了机器的内存当中.所以当我们程序要查询数据时,必须要从内存出来到磁盘里面去查找数据,然后将数据写回到内存当中.但是磁盘的io效率是远不如内存的,所有查找数据的快慢直接影响程序运行的效率. 而数据库加索引的主要目的就是为了使用一种合适的数据结构,可以使得查询数据的效率变高,减少磁盘io的次数,提升数据查找的速率,而不再是愣头青式的全局遍历. 那索引为啥要用B+Tree的数据结构呢?
MySQL Hash索引和B-Tree索引的区别

MySQL Hash索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引. 可能很多人又有疑问了,既然 Hash 索引的效率要比 B-Tree 高很多,为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢?任何事物都是有两面性的,Hash 索引也一样,虽然 Hash 索引效率高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊
浅析MysQL B-Tree 索引

B-Tree 索引不同的存储引擎也可能使用不同的存储结构,i如,NDB集群存储引擎内部实现使用了T-Tree结构存储这种索引,即使其名字是BTREE:InnoDB使用的是B+Tree. B-Tree通常一位这所有的值都是按顺序存储的,并且每一个叶子页道根的距离相同.下图大致反应了InnoDB索引是如何工作的. 为什么mysql索引要使用B+树,而不是B树,红黑树看完上面的文章就可以理解为何B-Tree索引能够快速访问数据了.因为存储引擎不再需要进行全表扫描获取需要的数据,叶子节点包含了所有元
获取 MySQL innodb B+tree 的高度的方法

前言 MySQL 的 innodb 引擎之所以使用 B+tree 来存储索引,就是想尽量减少数据查询时磁盘 IO 次数.树的高度直接影响了查询的性能.一般树的高度在 3~4 层较为适宜.数据库分表的目的也是为了控制树的高度.那么如何获取树的高度呢?下面使用一个示例来说明如何获取树的高度. 示例数据准备建表语句如下: CREATE TABLE `user` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(100) CHARAC
MySQL B-tree与B+tree索引数据结构剖析

目录一.产生的背景 1.1 进化要求二.B-tree 2.1 B-tree特性三.B+tree 3.1 B+tree特性四.结论一.产生的背景二叉查找树的查找时间复杂度是O(logN),整体的查询效率已经足够高了,那么为什么还会有B树和B+树的进化演进呢? 主要的原因是:二叉树可能会退化成一个线性树,造成磁盘IO次数增高的问题,当有大量的数据存储的时候,二叉查找树查询不能将所有的数据加载到内存中,只能逐一加载磁盘页,每个磁盘对应树的节点,造成大量的磁盘IO操作(最坏的情况IO次数为树
深入解析MySQL索引数据结构

目录概述索引数据结构二叉树红黑树 B-Tree B+Tree Hash 索引 InnoDB 索引实现(聚集) 索引文件和数据文件是分离的(非聚集) 聚集索引和非聚集索引联合/复合索引参考资料总结概述索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息. 索引数据结构二叉树二叉树(binary tree)是指树中节点的度不大于 2 的有序树,它是一种最简单且最重要的树.二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不
一步步带你学习设计MySQL索引数据结构

目录前言索引介绍索引设计目标索引设计迭代迭代一迭代二迭代三迭代四迭代小结索引结构总结聚簇索引非聚簇索引联合索引索引优点和缺点优点缺点总结前言 MySQL的索引是一个非常重要的知识点,也基本上是面试必考的一个技术点,所以非常重要.那你了解MySQL索引的数据结构是怎么样的吗?为什么要采用这样的数据结构? 现在化身为MySQL的架构师,一步步迭代设计出MySQL的索引结构,保证你再也忘记不了索引的结构了,轻松通过面试. 索引介绍 MySQL表中存储的数据量非常大,
Mysql中的Btree与Hash索引比较

mysql最常用的索引结构是btree(O(log(n))),但是总有一些情况下我们为了更好的性能希望能使用别的类型的索引.hash就是其中一种选择,例如我们在通过用户名检索用户id的时候,他们总是一对一的关系,用到的操作符只是=而已,假如使用hash作为索引数据结构的话,时间复杂度可以降到O(1).不幸的是,目前的mysql版本(5.6)中,hash只支持MEMORY和NDB两种引擎,而我们最常用的INNODB和MYISAM都不支持hash类型的索引. 不管怎样,还是要了解一下这两种索引的区别
MySQL怎么给字符串字段加索引

假设,你现在维护一个支持邮箱登录的系统,用户表是这么定义的: create table SUser( ID bigint unsigned primary key, email varchar(64), ... )engine=innodb; 由于要使用邮箱登录,所以业务代码中一定会出现类似于这样的语句: select f1, f2 from SUser where email='xxx'; 如果 email 这个字段上没有索引,那么这个语句就只能做全表扫描. 1)那我可以在邮箱地址这个
MySql中的存储引擎和索引

目录一.MySql的逻辑结构二.什么是存储引擎 MySQL支持的存储引擎三.操作四.数据库的索引索引的分类五.索引操作一.MySql的逻辑结构 MySQL体系结构分为四层:分别是连接层.服务层.存储引擎层.系统文件层. 连接层又称为客户端连接器(Client Connectors):提供与MySQL服务器建立的支持.连接池:管理.缓冲用户的连接,线程处理等需要缓存的需求. 服务层是MySQL Server的核心:主要包含系统管理和控制工具.SQL接口.解析器.查询优化器.缓存. 存
详解mysql中的冗余和重复索引

mysql允许在相同列上创建多个索引,无论是有意还是无意,mysql需要单独维护重复的索引,并且优化器在优化查询的时候也需要逐个地进行考虑,这会影响性能. 重复索引是指的在相同的列上按照相同的顺序创建的相同类型的索引,应该避免这样创建重复索引,发现以后也应该立即删除.但,在相同的列上创建不同类型的索引来满足不同的查询需求是可以的. CREATE TABLE test( ID INT NOT NULL PRIMARY KEY, A INT NOT NULL, B INT NOT NULL, UNI
MySQL查看、创建和删除索引的方法

本文实例讲述了MySQL查看.创建和删除索引的方法.分享给大家供大家参考.具体如下: 1．索引作用在索引列上,除了上面提到的有序查找之外,数据库利用各种各样的快速定位技术,能够大大提高查询效率.特别是当数据量非常大,查询涉及多个表时,使用索引往往能使查询速度加快成千上万倍. 例如,有3个未索引的表t1.t2.t3,分别只包含列c1.c2.c3,每个表分别含有1000行数据组成,指为1-1000的数值,查找对应值相等行的查询如下所示. SELECT c1,c2,c3 FROM t1,t2,t3
MySQL优化GROUP BY（松散索引扫描与紧凑索引扫描）

满足GROUP BY子句的最一般的方法是扫描整个表并创建一个新的临时表,表中每个组的所有行应为连续的,然后使用该临时表来找到组并应用累积函数(如果有).在某些情况中,MySQL能够做得更好,即通过索引访问而不用创建临时表. 为GROUP BY使用索引的最重要的前提条件是所有GROUP BY列引用同一索引的属性,并且索引按顺序保存其关键字.是否用索引访问来代替临时表的使用还取决于在查询中使用了哪部分索引.为该部分指定的条件,以及选择的累积函数. 由于GROUP BY 实
详解MySQL 8.0 之不可见索引

言 MySQL 8.0 从第一版release 到现在已经走过了4个年头了,8.0版本在功能和代码上做了相当大的改进和重构.和DBA圈子里的朋友交流,大部分还是5.6 ,5.7的版本,少量的走的比较靠前采用了MySQL 8.0.为了紧追数据库发展的步伐,能够尽早享受技术红利,我们准备将MySQL 8.0引入到有赞的数据库体系. 落地之前我们会对MySQL 8.0的新特性和功能,配置参数,升级方式,兼容性等等做一系列的学习和测试.以后陆陆续续会发布文章出来.本文算是MySQL 8.0新特性学习的