为什么MySQL数据库索引选择使用B+树?

在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出B树以及为什么MySQL数据库索引选择使用B+树!

学过数据结构的一般对最基础的树都有所认识,因此我们就从与我们主题更为相近的二叉查找树开始。

一、二叉查找树

(1)二叉树简介:

二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质:

1、任意节点左子树不为空,则左子树的值均小于根节点的值;

2、任意节点右子树不为空,则右子树的值均大于于根节点的值;

3、任意节点的左右子树也分别是二叉查找树;

4、没有键值相等的节点;

上图为一个普通的二叉查找树,按照中序遍历的方式可以从小到大的顺序排序输出:2、3、5、6、7、8。

对上述二叉树进行查找,如查键值为5的记录,先找到根,其键值是6,6大于5,因此查找6的左子树,找到3;而5大于3,再找其右子树;一共找了3次。如果按2、3、5、6、7、8的顺序来找同样需求3次。用同样的方法在查找键值为8的这个记录,这次用了3次查找,而顺序查找需要6次。计算平均查找次数得:顺序查找的平均查找次数为(1+2+3+4+5+6)/ 6 = 3.3次,二叉查找树的平均查找次数为(3+3+3+2+2+1)/6=2.3次。二叉查找树的平均查找速度比顺序查找来得更快。

(2)局限性及应用

一个二叉查找树是由n个节点随机构成,所以,对于某些情况,二叉查找树会退化成一个有n个节点的线性链。如下图:

大家看上图,如果我们的根节点选择是最小或者最大的数,那么二叉查找树就完全退化成了线性结构。上图中的平均查找次数为(1+2+3+4+5+5)/6=3.16次,和顺序查找差不多。显然这个二叉树的查询效率就很低,因此若想最大性能的构造一个二叉查找树,需要这个二叉树是平衡的(这里的平衡从一个显著的特点可以看出这一棵树的高度比上一个输的高度要大,在相同节点的情况下也就是不平衡),从而引出了一个新的定义-平衡二叉树AVL。

二、AVL树

(1)简介

AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1)。不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少,但查找多的情况。

从上面是一个普通的平衡二叉树,这张图我们可以看出,任意节点的左右子树的平衡因子差值都不会大于1。

(2)局限性

由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树。

(3)应用

1、Windows NT内核中广泛存在;

三、红黑树

(1)简介

一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是若平衡,可以推出,相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索、插入、删除操作多的情况下,我们就用红黑树。

(2)性质

1、每个节点非红即黑;

2、根节点是黑的;

3、每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的;

4、如果一个节点是红的,那么它的两儿子都是黑的;

5、对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;

6、每条路径都包含相同的黑节点;

(3)应用

1、广泛用于C++的STL中,Map和Set都是用红黑树实现的;

2、著名的Linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间;

3、IO多路复用epoll的实现采用红黑树组织管理sockfd,以支持快速的增删改查;

4、Nginx中用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器;

5、Java中TreeMap的实现;

四、B/B+树

说了上述的三种树:二叉查找树、AVL和红黑树,似乎我们还没有摸到MySQL为什么要使用B+树作为索引的实现,不要急,接下来我们就先探讨一下什么是B树。

(1)简介

我们在MySQL中的数据一般是放在磁盘中的,读取数据的时候肯定会有访问磁盘的操作,磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

总的来说,B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B树每个内节点有多个分支),与红黑树相比,在相同的的节点的情况下,一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成,而CPU的速度非常快,所以B树的操作效率取决于访问磁盘的次数,关键字总数相同的情况下B树的高度越小,磁盘I/O所花的时间越少。

注意B-树就是B树,-只是一个符号。

(2)B树的性质

1、定义任意非叶子结点最多只有M个儿子,且M>2;

2、根结点的儿子数为[2, M];

3、除根结点以外的非叶子结点的儿子数为[M/2, M];

4、每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)

5、非叶子结点的关键字个数=指向儿子的指针个数-1;

6、非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];

7、非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;

8、所有叶子结点位于同一层;

这里只是一个简单的B树,在实际中B树节点中关键字很多的,上面的图中比如35节点,35代表一个key(索引),而小黑块代表的是这个key所指向的内容在内存中实际的存储位置,是一个指针。

五、B+树

(1)简介

B+树是应文件系统所需而产生的一种B树的变形树(文件的目录一级一级索引,只有最底层的叶子节点(文件)保存数据)非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中,这不就是文件系统文件的查找吗?

我们就举个文件查找的例子:有3个文件夹a、b、c, a包含b,b包含c,一个文件yang.c,a、b、c就是索引(存储在非叶子节点), a、b、c只是要找到的yang.c的key,而实际的数据yang.c存储在叶子节点上。

所有的非叶子节点都可以看成索引部分!

(2)B+树的性质(下面提到的都是和B树不相同的性质)

1、非叶子节点的子树指针与关键字个数相同;

2、非叶子节点的子树指针p[i],指向关键字值属于[k[i],k[i+1]]的子树.(B树是开区间,也就是说B树不允许关键字重复,B+树允许重复);

3、为所有叶子节点增加一个链指针;

4、所有关键字都在叶子节点出现(稠密索引). (且链表中的关键字恰好是有序的);

5、非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层;

6、更适合于文件系统;

非叶子节点(比如5,28,65)只是一个key(索引),实际的数据存在叶子节点上(5,8,9)才是真正的数据或指向真实数据的指针。

(3)应用  

1、B和B+树主要用在文件系统以及数据库做索引,比如MySQL;

六、B/B+树性能分析

n个节点的平衡二叉树的高度为H(即logn),而n个节点的B/B+树的高度为logt((n+1)/2)+1;

若要作为内存中的查找表,B树却不一定比平衡二叉树好,尤其当m较大时更是如此。因为查找操作CPU的时间在B-树上是O(mlogtn)=O(lgn(m/lgt)),而m/lgt>1;所以m较大时O(mlogtn)比平衡二叉树的操作时间大得多。因此在内存中使用B树必须取较小的m。(通常取最小值m=3,此时B-树中每个内部结点可以有2或3个孩子,这种3阶的B-树称为2-3树)。

七、为什么说B+树比B树更适合数据库索引?

1、 B+树的磁盘读写代价更低:B+树的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对B树更小,如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对IO读写次数就降低了。

2、B+树的查询效率更加稳定:由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

3、由于B+树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引。

PS:我在知乎上看到有人是这样说的,我感觉说的也挺有道理的:

他们认为数据库索引采用B+树的主要原因是:B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作或者说效率太低。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

时间: 2019-02-26

mysql+spring+mybatis实现数据库读写分离的代码配置

场景:一个读数据源一个读写数据源. 原理:借助spring的[org.springframework.jdbc.datasource.lookup.AbstractRoutingDataSource]这个抽象类实现,看名字可以了解到是一个路由数据源的东西,这个类中有一个方法 /** * Determine the current lookup key. This will typically be * implemented to check a thread-bound transaction

利用MySQL主从配置实现读写分离减轻数据库压力

大型网站为了软解大量的并发访问,除了在网站实现分布式负载均衡,远远不够.到了数据业务层.数据访问层,如果还是传统的数据结构,或者只是单单靠一台服务器扛,如此多的数据库连接操作,数据库必然会崩溃,数据丢失的话,后果更是 不堪设想.这时候,我们会考虑如何减少数据库的联接,一方面采用优秀的代码框架,进行代码的优化,采用优秀的数据缓存技术如:memcached,如果资金丰厚的话,必然会想到假设服务器群,来分担主数据库的压力.Ok切入今天文章主题,利用MySQL主从配置,实现读写分离,减轻数据库压力.这种

MySQL存储引擎MyISAM与InnoDB区别总结整理

1.MySQL默认存储引擎的变迁 在MySQL 5.1之前的版本中,默认的搜索引擎是MyISAM,从MySQL 5.5之后的版本中,默认的搜索引擎变更为InnoDB. 2.MyISAM与InnoDB存储引擎的主要特点 MyISAM存储引擎的特点是:表级锁.不支持事务和全文索引,适合一些CMS内容管理系统作为后台数据库使用,但是使用大并发.重负荷生产系统上,表锁结构的特性就显得力不从心: 以下是MySQL 5.7 MyISAM存储引擎的版本特性: InnoDB存储引擎的特点是:行级锁.事务安全(A

Ubuntu上mysql的安装及使用(通用版)

不管是哪个版本的Ubuntu,安装mysql数据库基本上都是大同小异.下面介绍一下具体的安装步骤: 1.打开终端,并取得root权限 2.在终端输入: apt-get install mysql-server apt-get install mysql-client apt-get install libmysqlclient-dev 安装过程中,必要的地方需要输入"Y"进行确定. 上面这三条命令执行完以后,要想检测mysql是否安装成功,可输入下面的命令进行查看: netstat -

Mysql忘记密码的几种解决方案

解决办法1 卸载完全,删除所有数据,先关闭跟MySql所有有关的进程,进入命令行(cmd)中输入taskkill /f /im mysqld-nt.exe 然后找到MySql的根目录删除即可 解决办法2 在命令行里面输出密码或者更更改密码 .在命令行运行:taskkill /f /im mysqld-nt.exe 下面的操作是操作mysql中bin目录下的一些程序,如果没有配置环境变量的话,需要切换到mysql的bin 目录下执行如下语句.不然无效 .继续在命令行运行:mysqld-nt --s

Mysql常用函数大全(分类汇总讲解)

一.数学函数 ABS(x)   返回x的绝对值 BIN(x)   返回x的二进制(OCT返回八进制,HEX返回十六进制) CEILING(x)   返回大于x的最小整数值 EXP(x)   返回值e(自然对数的底)的x次方 FLOOR(x)   返回小于x的最大整数值 GREATEST(x1,x2,...,xn)返回集合中最大的值 LEAST(x1,x2,...,xn)      返回集合中最小的值 LN(x)                    返回x的自然对数 LOG(x,y)返回x的以y

阿里云esc服务器Docker部署单节点Mysql的讲解

1.下载加速版msyql   docker pull hub.c.163.com/library/mysql:5.7 2.更名 docker tag hub.c.163.com/library/mysql:5.7 mysql:5.7 3.启动 docker run -it --rm --name mysql -e MYSQL_ROOT_PASSWORD=123456 -p 3306:3306 -d mysql 4.设置mysql远程登录 docker exec -it mysql bash my

MySQL存储文本和图片的方法

Oracle中大文本数据类型 Clob 长文本类型 (MySQL中不支持,使用的是text) Blob 二进制类型 MySQL数据库 Text 长文本类型 TINYTEXT: 256 bytes TEXT: 65,535 bytes => ~64kb MEDIUMTEXT: 16,777,215 bytes => ~16MB LONGTEXT: 4,294,967,295 bytes => ~4GB Blob 二进制类型 例如: 建表 CREATE TABLE test( id INT

Mysql如何适当的添加索引介绍

这里先简单介绍一下索引: 添加索引是为了提高数据库查询性能,索引是最物美价廉的东西了,不用加内存,不用改程序,不用调sql,只要执行个正确的create index ,查询的速度就可能提高百倍千倍,这可是有诱惑力的,可是天下没有没费的午餐,查询的速度的提高是以牺牲insert update delete的速度为代价的.而且索引大小一般是数据的三分之一  ,再加上索引要加载进内存的,如果全部字段都加索引会以牺牲内存为代价的,所以才要设当的添加索引. 这里简单介绍一下mysql中常用索引: 在添加索

将图片储存在MySQL数据库中的几种方法

通常对用户上传的图片需要保存到数据库中. 解决方法一般有两种: 1.将图片保存的路径存储到数据库: 2.将图片以二进制数据流的形式直接写入数据库字段中. 以下为具体方法: 一.保存图片的上传路径到数据库: string uppath="";//用于保存图片上传路径 //获取上传图片的文件名 string fileFullname = this.FileUpload1.FileName; //获取图片上传的时间,以时间作为图片的名字可以防止图片重名 string dataName = D

Python使用pymysql从MySQL数据库中读出数据的方法

python3.x已经不支持mysqldb了,支持的是pymysql 使用pandas读取MySQL数据时,使用sqlalchemy,出现No module named 'MySQLdb'错误. 安装:打开Windows PowerShell,输入pip3 install PyMySQL即可 import pymysql.cursors import pymysql import pandas as pd #连接配置信息 config = { 'host':'127.0.0.1', 'port'

安全快速修改Mysql数据库名的5种方法

1. RENAME DATABASE db_name TO new_db_name这个..这个语法在mysql 5.1.7中被添加进来,到了5.1.23又去掉了.据说有可能丢失数据.还是不要用的好.详见: http://dev.mysql.com/doc/refman/5.1/en/rename-database.html 2.如果所有表都是MyISAM类型的话,可以改文件夹的名字关闭mysqld把data目录中的db_name目录重命名为new_db_name开启mysqld 3.重命名所有的

MySQL数据库中的安全设置方案

随着网络的普及,基于网络的应用也越来越多.网络数据库就是其中之一.通过一台或几台服务器可以为很多客户提供服务,这种方式给人们带来了很多方 便,但也给不法分子造成了可乘之机.由于数据都是通过网络传输的,这就可以在传输的过程中被截获,或者通过非常手段进入数据库.由于以上原因,数据库安全 就显得十分重要.因此,本文就以上问题讨论了MySQL数据库在网络安全方面的一些功能. 帐户安全 帐户是MySQL最简单的安全措施.每一帐户都由用户名.密码以及位置(一般由服务器名.IP或通配符)组成.如用户john从

如何基于java向mysql数据库中存取图片

这篇文章主要介绍了如何基于java向mysql数据库中存取图片,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 学mysql的时候都是做个表格,放的也都是文字内容,虽然我知道长篇的文章和图片或者视频的都是用过文件夹的方式存储的,再讲文件路径存进数据库中.但还是想试试直接往mysql数据库中存取图片.这里我用的是java语言和jdbc实现的 mysql数据库中有一个类型是Blob类型,这是一个二进制类型,通常我们会将图片或音像文件转成二进制再存入数

php将图片保存入mysql数据库失败的解决方法

本文实例分析了php将图片保存入mysql数据库失败的解决方法.分享给大家供大家参考.具体分析如下: 图片保存数据库并不是一个明智的做法,我们多半是把图片保存到服务器,然后把图片地址保存到数据库,这样我们每次只要读出图片地址就可以显示了,但下面我还是来介绍一个图片保存到mysql数据库的问题解决办法,代码如下: 复制代码 代码如下: require 'class/db.php'; $fileName = "a1.jpg"; $fp = fopen($fileName, "r&

mysql数据库中的information_schema和mysql可以删除吗?

新装的mysql里面有两个数据库:information_schema 和 mysql  .他们是干么用的?可以删除么?当然是不可以删除的. 1.information schema 是mysql系统用的所有字典信息,包括数据库系统有什么库,有什么表,有什么字典,有什么存储过程等所有对象信息和进程访问.状态信息.一旦删除该数据库系统将无法使用. 2.mysql数据库是保存系统有关的权限,对象和状态信息.同样是不能删除的.并且这两个数据库都很小,不占用空间,你为什么要删除呢.? mysql数据库中

如何在Java程序中访问mysql数据库中的数据并进行简单的操作

在上篇文章给大家介绍了Myeclipse连接mysql数据库的方法,通过本文给大家介绍如何在Java程序中访问mysql数据库中的数据并进行简单的操作,具体详情请看下文. 创建一个javaProject,并输入如下java代码: package link; import java.sql.*; /** * 使用JDBC连接数据库MySQL的过程 * DataBase:fuck, table:person: * 使用myeclipse对mysql数据库进行增删改查的基本操作. */ public

浅谈mysql数据库中的换行符与textarea中的换行符

1. mysql数据库中的换行符 在mysql数据库中, 其换行符为\n 即 char(10), 在python中为chr(10) 2. textarea中的换行符 textarea中的换行符为\r\n 3. web应用中换行符转换 以下是python django web的处理: # data为textarea获取的数据, 其中包括换行符`\r\n`, 以下是过渡处理 data = data.replace('\r\n', '\n') # 或 data = data.replace('\r\n

MySQL数据库中把int转化varchar引发的慢查询

最近一周接连处理了2个由于int向varchar转换无法使用索引,从而引发的慢查询. CREATE TABLE `appstat_day_prototype_201305` ( `day_key` date NOT NULL DEFAULT '1900-01-01', `appkey` varchar(20) NOT NULL DEFAULT '', `user_total` bigint(20) NOT NULL DEFAULT '0', `user_activity` bigint(20)