
- 提出时间
- 1970年
- 别 称
- B-树、B_树
- 提出者
- R.Bayer和E.mccreight
- 应用学科
- 计算机
- 中文名
- B树
- 适用领域范围
- 编程
- 外文名
- B tree
-
2021-12-15 15:17:49
文章目录
树基础知识回顾
排序二叉树:左 < 根< 右
B 树:有序数组 + 多叉平衡树,节点存储关键字、数据、指针;
B+ 树:有序数组链表 + 多叉平衡树,非叶子节点存储指针、关键字,不存储数据;
红黑树:红黑树是一种不大严格的平衡树(平衡树要求太高)红黑树
红黑树:
红黑树(一棵自平衡的排序二叉树)五大特性:
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点,即空结点是黑的。
4)如果一个结点是红的,那么它的俩个儿子都是黑的。
5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。场景
1)广泛用于C++的STL中,map和set都是用红黑树实现的.
2)著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存
区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址
虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.
3)IO多路复用epoll的实现采用红黑树组织管理sockfd,以支持快速的增删改查.
4)ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
5)java中的TreeSet,TreeMap左旋和右旋可以参考:红黑树旋转过程
拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?
之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。
而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持 平衡 是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于 8 的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。平衡树是为了防止二叉查找树退化为链表,而红黑树在维持平衡以确保 O(log2(n)) 的同时,不需要频繁着调整树的结构;
当我们进行插入或者删除操作时所作的一切操作都是为了调整树使之符合这五条性质。
下面我们先介绍两个基本操作,旋转。
旋转的目的是将节点多的一支出让节点给另一个节点少的一支,旋转操作在插入和删除操作中经常会用到
b树、b+树
B 树即:多路平衡查找树;
B 树的巧妙之处在于:
- 将一个节点的大小设置为一页的大小;
- 一个节点可以存放多个关键字(多叉树);
- 自平衡;
这 3 点结合起来就可以做到:
- 一个节点大小为一页,被加载进内存时,这些关键字在进行对比,找出需要 leftChild 还是 rightChild 时,都是有用的(如最右侧时需要对比所有节点);
- 一个节点可以存储多个关键字,有效降低了树的高度;
B+ 树的巧妙之处在于:
- 非叶子节点不存储数据,进一步增大了一页中存储关键字的数量;
- 叶子节点中存储数据且存在指向下一页的链表指针,可以使用顺序查询(支持范围查询);
b+树比b树的优点:
1.顺序查找 范围查找 排序查找能力强
2.IO的效率更高,因为非叶结点不存储数据
3.基于索引树的全量数据扫描能力更高
为什么不能使用二叉树来存储数据库索引
先说结论:
- 平衡二叉树进行插入/删除时,大概率需要通过左旋/右旋来维持平衡;
- 旋转需要加载整个树,频繁旋转效率低;
- 二叉树的 I/O 次数近似为 O(log2(n));
- 范围查询时,二叉树的时间复杂度会退化成 O(n);
- 二叉树退化成链表时,时间复杂度也近似退化成了 O(n);
- 二叉树无法使用磁盘预读功能;
其实单论范围查询,在关系型数据库中就基本没有使用二叉树的可能了。但是为了加深对知识的了解,来看看其他的原因。
先剔除掉范围查询的情况,原因 1、2、6 可以通过红黑树来解决,那么其实就剩下 2 个原因:
- I/O 次数对比;
- 磁盘预读功能的利用;
B/B+树的索引数量
B 树的节点中存储:指针、关键字(主键)、数据
B+ 树的非叶子节点:指针、关键字
B+树的叶子节点:指针(链表)、关键字、数据注意,这里不是绝对的,比如有的 B+ 树中叶子节点存储的不是数据,而是指向数据的指针。查询到指针之后再去对应地址取出数据,但是这样应该会增加一次 I/O 吧,应该也是在数据量和 I/O 次数之间做了取舍,具体先不讨论。
以 Sqlite3.12 之后为例,page_size = 16k,假设指针为 8 byte,假设关键字类型占 8 byte,假设数据占 1 KB;
B 树的一个节点:
一页能存储的数据量为:16kb / (1KB+8byte+8byte) ≈ 16;
高度为 3 的 B 树能存储 16 x16 x16 = 4096 条数据
相比于二叉树的 1 个而言,确实有效降低了树的层级。而且上述是假设数据为 1KB,如果数据没那么大,高度为 3 的 B 树能存储更多的数据,但是如果用在大型数据库索引上还是不够。
B+树的核心在于非叶子节点不存储数据。
这样做可以减少非叶子结点占用的空间,增大一页所能存储的数据量,最大程度减少树的层级。
仍然是以上假设,假如树的高度为 3 ,那么就有两层存储关键字+指针,一层叶子节点来存储实际数据。
一页能存储的关键字为:16 * 1024 / (8 + 8) = 1024
一页能存储的数据量为:16KB / (1KB + 8byte + 8byte) = 16
(这里计算不完全准确,实际情况应该是1页数据中只有一个链表指针指向下一页)
能存储的关键字为:1024 * 1024 = 1048576;因为端节点又有 1024 个指针,这些指针可以指向一个页,页中存储数据,也就是叶子节点,一页能存储 16 个叶子节点,所以总共能索引的数据量为 1048576 * 16 ≈ 1600万;如果高度为 4 ,则再乘以 1024 约为 17亿……
注意:b+树上有两个头指针,一个指向根节点,一个指向关键字最小的叶子结点,而且所有叶子结点之间是一种链式环结构,因此可以用b+树进行两种查找运算:一种是对于主键的范围查找和分类查找,一种是从根节点开始进行随机查找。
上述推理中,理解终端节点的指针指向一个页,页中存储着关键字 + 数据 + 链表指针是关键。
索引
索引是关系型数据库为了加速对表中行数据检索的(磁盘存储的)数据结构
一般来说索引本身也很大,不可能全部存储在内存中,因此索引往往是存储在磁盘上的文件中的(可能存储在单独的索引文件中,也可能和数据一起存储在数据文件中)。
我们通常所说的索引,包括聚集索引、覆盖索引、组合索引、前缀索引、唯一索引等,没有特别说明,默认都是使用B+树结构组织(多路搜索树,并不一定是二叉的)的索引。索引的基本原理
索引用来快速地寻找那些具有特定值的记录。如果没有索引,一般来说执行查询时遍历整张表。
索引的原理:就是把无序的数据变成有序的查询- 把创建了索引的列的内容进行排序
- 对排序结果生成倒排表
- 在倒排表内容上拼上数据地址链
- 在查询的时候,先拿到倒排表内容,再取出数据地址链,从而拿到具体数据
索引的常用数据结构?
索引的数据结构和具体存储引擎的实现有关, 在MySQL中使用较多的索引有Hash索引,B+树索引等,而我们经常使用的InnoDB存储引擎的默认索引实现为:B+树索引什么是聚簇(集)索引?
innodb存储引擎在进行数据插入的时候数据必须要跟某一个索引列存储在一起,这个索引列可以是主键,如果没有主键则选择唯一键,如果没有唯一键选择6字节的rowid来进行存储。
innodb中有聚簇索引也有非聚簇索引,myisam只有非聚簇索引
非聚簇索引的叶子结点存储的数据不再是整行的记录而是聚簇索引的id值
表数据文件本身就是按b+树组织的一个索引结构文件
聚集索引-指叶结点包含了完整的数据记录
在B+树的索引中,叶子节点可能存储了当前的key值**,也可能存储了当前的key值以及整行的数据,这就是聚簇索引和非聚簇索引.** 在InnoDB中,只有主键索引是聚簇索引,如果没有主键,则挑选一个唯一键建立聚簇索引.如果没有唯一键,则隐式的生成一个键来建立聚簇索引.当查询使用聚簇索引时,在对应的叶子节点,可以获取到整行数据,因此不用再次进行回表查询.
对于InnoDB表而言,MySQL的非聚簇索引统称为“辅助索引”(secondary index),辅助索引的“表记录指针”称为“书签”(bookmark),实际上是主键值,如图3-32所示,可以看到,所有的辅助索引都包含主键列,所有的InnoDB表都是通过主键来聚簇的。
●非聚簇索引一定会回表查询吗?
不一定,这涉及到查询语句所要求的字段是否全部命中了索引,如果全部命中了索引,那么就不必再进行回表查询.
举个简单的例子,假设我们在员工表的年龄上建立了索引,那么当进行select age from employee where age < 20的查询时,在索引的叶子节点上,已经包含了age信息,不会再次进行回表查询.● InnoDB存储引擎的表支持聚簇索引。由于创建聚簇索引时需要对“索引”中的数据以及表中的数据进行排序,为了避免更新数据(例如插入数据)耗费过多的时间,建议将InnoDB表的主键设置为自增型字段。
为什么非主键索引叶子节点存储的是主键值: 一致性和节省存储空间
mysql聚簇和非聚簇索引的区别
都是B+树的数据结构
聚簇索引:将数据存储与索引放到了一块、并且是按照一定的顺序组织的,找到索引也就找到了数据,数据的物理存放顺序与索引顺序是一致的,即:只要索引是相邻的,那么对应的数据一定也是相邻地存放在磁盘上的
非聚簇索引:叶子节点不存储数据、存储的是数据行地址,也就是说根据索引查找到数据行的位置再取磁盘查找数据,这个就有点类似一本树的目录,比如我们要找第三章第一节,那我们先在这个目录里面找,找到对应的页码后再去对应的页码看文章。优势:
1、查询通过聚簇索引可以直接获取数据,相比非聚簇索引需要第二次查询(非覆盖索引的情况下)效率要高
2、聚簇索引对于范围查询的效率很高,因为其数据是按照大小排列的
3、聚簇索引适合用在排序的场合,非聚簇索引不适合
劣势:
1、维护索引很昂贵,特别是插入新行或者主键被更新导至要分页(page split)的时候。建议在大量插入新行后,选在负载较低的时间段,通过OPTIMIZE TABLE优化表,因为必须被移动的行数据可能造成碎片。使用独享表空间可以弱化碎片
2、表因为使用UUId(随机ID)作为主键,使数据存储稀疏,这就会出现聚簇索引有可能有比全表扫面更慢,所以建议使用int的auto_increment作为主键
3、如果主键比较大的话,那辅助索引将会变的更大,因为辅助索引的叶子存储的是主键值;过长的主键值,会导致非叶子节点占用占用更多的物理空间📣📣【innodb中怎么设置索引】InnoDB中一定有主键,主键一定是聚簇索引,不手动设置、则会使用unique索引,判断表中是否有非空的唯一索引(Unique NOT NULL),若有,则该列即为主键(当表中有多个非空唯一索引时,InnoDB 存储引擎将选择建表时第一个定义的非空唯一索引,没有unique索引,则会使用数据库内部的一个行的隐藏id来当作主键索引。在聚簇索引之上创建的索引称之为辅助索引,辅助索引访问数据总是需要二次查找,非聚簇索引都是辅助索引,像复合索引、前缀索引、唯一索引,
辅助索引叶子节点存储的不再是行的物理位置,而是主键值
MyISM使用的是非聚簇索引,没有聚簇索引,非聚簇索引的两棵B+树看上去没什么不同,节点的结构完全一致只是存储的内容不同而已,主键索引B+树的节点存储了主键,辅助键索引B+树存储了辅助键。表数据存储在独立的地方,这两颗B+树的叶子节点都使用一个地址指向真正的表数据,对于表数据来说,这两个键没有任何差别。由于索引树是独立的,通过辅助键检索无需访问主键的索引树。
如果涉及到大数据量的排序、全表扫描、count之类的操作的话,还是MyISAM占优势些,因为索引所占空间小,这些操作是需要在内存中完成的。
InnoDB存储引擎的默认索引实现为:B+树索引。对于哈希索引来说,底层的数据结构就是哈希表,因此在绝大多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快;其余大部分场景,建议选择B+Tree索引。
(1)可以看到,InnoDB的B+树索引的结点就是InnoDB的数据页,这些结点通过File Header中的上一页、下一页左右相连成为一个双向链表;
(2)B+树只有叶子结点才存放数据,非叶子结点的记录头的record_type字段都置为1,叶子节点的记录的record_type字段则是0(除了系统插入的最大记录、最小记录);
(3)非叶子结点的只有两个字段有效:页号+该页号的页内记录的最小主键id(注意图中红字部分)。这样根据要查的目标记录的id就可以找到它属于拿个页了,然后在页内根据要查的记录主键二分找到最相近的槽号,通过槽号到记录组后就个位数的记录了,直接遍历即可。
(4)二级索引或叫辅助索引也是类似的结构,只是把按照主键寻找改成按照索引字段+主键寻找结点而已(加主键不仅是为了回访主键索引,也是为了保证非叶子结点中记录的唯一性,因为索引字段可能重复)。
二级索引的叶子结点不记录所有数据,只有索引字段和主键,确定查找目标后需要拿主键回访主键索引。
(5)为c1、c2建立联合索引,也就是二级索引。优先按照建立索引时的左边字段进行排序,即c1。当c1字段相同时,在这些c1相同的连续一串结点里再根据c2字段进行索引。这也是左前缀原则的原理。
B树和B+树的不同点及思考
(1)我们知道从磁盘搬运数据到内存一般都是几KB的搬,避免频繁磁盘IO。所以InnoDB选择一个页作为一个结点,一次性运一个结点进内存,然后在内存中二分查找、遍历找到对应记录。B树的每个结点里的每条记录都是带有完整的一行数据的,这就导致了一个结点中可存储的记录条数变少了,就意味着一个结点开的叉变少了很多,就意味着整个索引树的高度变大了,这显然是不好的。基于此,B+树让全部数据存到叶子结点中,其他结点不存放数据,每个非叶子结点的分叉大大增多,代价就是每次查找都必须走到叶子结点。4层B+树已经可以存很多很多记录了,5到6层已经是极限了。
(2)B+树的所以数据都存到叶子结点,还有双向的指针将这些结点组成双向链表,非常适合范围查找。
b+树和哈希索引
innodb通过b+树结构对主键创建索引,然后叶子节点中存储记录,如果没有主键,那么会选择唯一键,如果没有唯一键那么会生成一个六字节的row_id作为主键。
如果创建索引的键是其他字段,那么在叶子节点中存储的是该记录的主键,然后再通过主键索引找到对应的记录,叫做回表。
注意:b+树上有两个头指针,一个指向根节点,一个指向关键字最小的叶结点,而且所有的叶结点之间是一种链式环结构,因此可以对b+树进行两种查找运算:一种是对于主键的范围查找和分页查找,另一种是从根节点开始进行随机查找。B+树是一个平衡的多叉树,从根节点到每个叶子节点的高度差值不超过1,而且同层级的节点间有指针相互链接。在B+树上的常规检索,从根节点到叶子节点的搜索效率基本相当,不会出现大幅波动,而且基于索引的顺序扫描时,也可以利用双向指针快速左右移动,效率非常高。因此,B+树索引被广泛应用于数据库、文件系统等场景。
二级索引
二级索引:叶子节点中存储主键值,每次查找数据时,根据索引找到叶子节点中的主键值,根据主键值再到聚簇索引中得到完整的一行记录。
问题:
1.相比于叶子节点中存储行指针,二级索引存储主键值会占用更多的空间,那为什么要这样设计呢?
InnoDB在移动行时,无需维护二级索引,因为叶子节点中存储的是主键值,而不是指针。
二级索引存储主键值而不是存储行指针的优点与缺点
优点
减少了出现行移动或者数据页分裂时二级索引的维护工作(当数据需要更新的时候,二级索引不需要修改,只需要修改聚簇索引,一个表只能有一个聚簇索引,其他的都是二级索引,这样只需要修改聚簇索引就可以了,不需要重新构建二级索引)
缺点
- 二级索引体积可能会变大,因为二级索引中存储了主键的信息
- 二级索引的访问需要两次索引查找。第一次通过查找 二级索引 找二级索引中叶子节点存储的 主键的值;第二次通过这个主键的值去 聚簇索引 中查找对应的行
(疑惑:为什么存储指针的时候就需要修改索引了?是因为指针中直接指向了物理文件位置吗?)
2.那么InnoDB有了聚簇索引,为什么还要有二级索引呢?
聚簇索引的叶子节点存储了一行完整的数据,而二级索引只存储了主键值,相比于聚簇索引,占用的空间要少。当我们需要为表建立多个索引时,如果都是聚簇索引,那将占用大量内存空间,所以InnoDB中主键所建立的是聚簇索引,而唯一索引、普通索引、前缀索引等都是二级索引。
3.为什么一般情况下,我们建表的时候都会使用一个自增的id来作为我们的主键?
InnoDB中表中的数据是直接存储在主键聚簇索引的叶子节点中的,每插入一条记录,其实都是增加一个叶子节点,如果主键是顺序的,只需要把新增的一条记录存储在上一条记录的后面,当页达到最大填充因子的时候,下一跳记录就会写入新的页中,这种情况下,主键页就会近似于被顺序的记录填满。
若表的主键不是顺序的id,而是无规律数据,比如字符串,InnoDB无法简单的把一行记录插入到索引的最后,而是需要找一个合适的位置(已有数据的中间位置),甚至产生大量的页分裂并且移动大量数据,在寻找合适位置进行插入时,目标页可能不在内存中,这就导致了大量的随机IO操作,影响插入效率。除此之外,大量的页分裂会导致大量的内存碎片。
更多相关内容 -
B树和B+树详解
2021-05-24 09:43:53Mysql调优之B树和B+ 树详解B树 和 B+树详解
在学习数据库调优相关知识的时候,我们发现数据库系统普遍采用B-/+Tree作为索引结构,例如MySQL的InnoDB引擎使用的数据结构是B+Tree,因此我们需要对BTree和B+Tree理解清楚,才能更好的理解数据库的索引机制。注意:容易混淆的B树即为B-树。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是一种树。而事实上是,B-tree就是指的B树,目前理解B的意思为平衡。
二叉搜索树(BST)
平衡二叉搜索树(AVL):便于动态保持平衡的二叉搜索树
有关AVL树的相关内容可以查看数据结构与算法中的二叉树与二叉搜索树的内容。1 B树
二叉树是二分树,
多分树
是二叉树的推广。多分树主要适用于静态的索引数据文件
,在插入和删除的时候需要把插入位置之后的每个记录都要向后移动,从而导致增加新的索引项和索引页块,需要对外存上的页块进行大量的调整。因此对于经常需要插入和删除的动态索引顺序文件,使用多分树并不合适,需要采用动态索引结构
,即B树和B+树
。
B树是一种自平衡树,是AVL树的一般化,它维护有序数据并允许以对数时间进行搜索,顺序访问,插入和删除。与AVL树不同的是,B树非常适合读取和写入相对较大的数据块(如光盘)的存储系统。它通常用于数据库和文件系统。1.1 B树的定义
一颗m阶的B树满足如下条件:
- 每个节点最多只有m个子节点。
- 除根节点外,每个非叶子节点具有至少有 m/2(向下取整)个子节点。
- 非叶子节点的根节点至少有两个子节点。
- 有k颗子树的非叶节点有k-1个键,键按照递增顺序排列。
- 叶节点都在同一层中。
(1)什么是B树的阶 ?
B树中一个节点的子节点数目的最大值,用m表示,假如最大值为4,则为4阶,如图,所有节点中,节点[13,16,19]拥有的子节点数目最多,四个子节点(灰色节点),所以可以定义上面的图片为4阶B树。(2)什么是根节点 ?
节点【10】即为根节点,特征:根节点拥有的子节点数量的上限和内部节点相同,如果根节点不是树中唯一节点的话,至少有俩个子节点(不然就变成单支了)。在m阶B树中(根节点非树中唯一节点),那么有关系式2<= M <=m,M为子节点数量;包含的元素数量 1<= K <=m-1,K为元素数量。(3)什么是内部节点 ?
节点【13,16,19】、节点【3,6】都为内部节点,特征:内部节点是除叶子节点和根节点之外的所有节点,拥有父节点和子节点。假定m阶B树的内部节点的子节点数量为M,则一定要符合(m/2)<= M <=m关系式,包含元素数量M-1;包含的元素数量 (m/2)-1<= K <=m-1,K为元素数量。m/2向上取整。(4)什么是叶子节点?
节点【1,2】、节点【11,12】等最后一层都为叶子节点,叶子节点对元素的数量有相同的限制,但是没有子节点,也没有指向子节点的指针。特征:在m阶B树中叶子节点的元素符合(m/2)-1<= K <=m-1。1.2 B树出现的目的
B树的出现是为了
弥补不同的存储级别之间的访问速度上的巨大差异,实现高效的 I/O
。平衡二叉树的查找效率是非常高的,并可以通过降低树的深度来提高查找的效率。但是当数据量非常大,树的存储的元素数量是有限的,这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况
。B树是解决这个问题的很好的结构。1.3 B树的检索、插入和删除
1.3.1 检索
根据要查找的关键码key,在根节点的关键码集合中进行顺序或二分法检索,若key = ki,则检索成功;
否则,key一定在某 ki 和 ki+1 之间,用一个指针在所指节点继续查找,重复上述检索过程,直到检索成功;或指针为空,则检索失败。
整个检索过程中访外次数与B树的高度成正比
。1.3.2 插入
针对m阶高度h的B树,插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素。
- 若该节点元素个数小于m-1,直接插入;
- 若该节点元素个数等于m-1,引起节点分裂;以该节点中间元素为分界,取中间元素(偶数个数,中间两个随机选取)插入到父节点中;
- 重复上面动作,直到所有节点符合B树的规则;最坏的情况一直分裂到根节点,生成新的根节点,高度增加1。
上面三点为插入动作的核心,接下来以5阶B树为例,详细讲解插入的动作。
5阶B树关键点:
2<=根节点子节点个数<=5
3<=内节点子节点个数<=5
1<=根节点元素个数<=4
2<=非根节点元素个数<=41.3.3 删除
首先查找B树中需删除的元素,如果该元素在B树中存在,则将该元素在其结点中进行删除;删除该元素后,首先判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中,然后是移动之后的情况;如果没有,直接删除。
- 某结点中元素数目小于(m/2)-1,(m/2)向上取整,则需要看其某相邻兄弟结点是否丰满;
- 如果丰满(结点中元素个数大于(m/2)-1),则向父节点借一个元素来满足条件;
- 如果其相邻兄弟都不丰满,即其结点数目等于(m/2)-1,则该结点与其相邻的某一兄弟结点进行“合并”成一个结点;
接下来还以5阶B树为例,详细讲解删除的动作:
关键要领,元素个数小于2(m/2 -1)就合并,大于4(m-1)就分裂
如图依次删除依次删除【8】,【20】,【18】,【5】
2 B+树
B+树是应文件系统所需而产生的B树的变形树,那么可能一定会想到,既然有了B树,又出一个B+树,那B+树必然是有很多优点的。
2.1 B+树的定义
一颗m阶的B+树满足如下条件:
- 每个节点最多只有m个子节点。
- 除根节点外,每个非叶子节点具有至少有 m/2(向下取整)个子节点。
- 非叶子节点的根节点至少有两个子节点。
- 有k颗子树的非叶节点有k个键,键按照递增顺序排列。
- 叶节点都在同一层中。
说明:
每个叶节点中至少包含 m/2(向下取整)个关键码,所有主文件记录的索引项都存放在B+树的叶节点中。所有内部节点都看成是索引的索引。节点中仅包含它的各个子节点中最大(或最小)关键码的分界值以及指向子节点的指针。
2.2 B+树与B树的差异
B+树 B树 有m颗子树的节点中含有 m 个关键码 有m颗子树的节点中含有 m-1 个关键码 所有的叶子结点中包含了完整的索引信息,包括指向含有这些关键字记录的指针,中间节点每个元素不保存数据,只用来索引 B树中非叶子节点的关键码与叶子结点的关键码均不重复,它们共同构成全部的索引信息 所有的非叶子节点可以看成是高层索引, 结点中仅含有其子树根结点中最大(或最小)关键字 B 树的非叶子节点包含需要查找的有效信息 2.3 B+树的检索、插入和删除
检索
在B+树中检索关键码key的方法与B树的检索方式相似,但若在内部节点中找到检索的关键码时,检索并不会结束,要继续找到B+树的叶子结点为止。
插入
与B树的插入操作相似,总是插到叶子结点上。当叶节点中原关键码的个数等于m时,该节点分裂成两个节点,分别使关键码的个数为 (m+1)/2 (向上取整)和 (m+1)/2 (向下取整)。
删除
仅在叶节点删除关键码。若因为删除操作使得节点中关键码数少于 m/2(向下取整)时,则需要调整或者和兄弟节点合并。合并的过程和B树类似,区别是父节点中作为分界的关键码不放入合并后的节点中。3 磁盘IO与B树
3.1 BTree的高度
BTree上大部分操作所需的磁盘读取次数与B树的高度成正比
。一棵含有N个总关键字数的m阶的B树的最大高度是多少?
log(m/2)(N+1)/2 + 1 ,log以(m/2)为底,(N+1)/2的对数再加1.
3.2 磁盘IO与预读
计算机存储设备一般分为两种:
内存储器(main memory)和外存储器(external memory)
。(1)内存储器为内存,内存存取速度快,但容量小,价格昂贵,而且不能长期保存数据(在不通电情况下数据会消失)。
(2)外存储器即为磁盘读取,磁盘读取数据靠的是机械运动,每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分,寻道时间指的是磁臂移动到指定磁道所需要的时间,主流磁盘一般在5ms以下;旋转延迟就是我们经常听说的磁盘转速,比如一个磁盘7200转,表示每分钟能转7200次,也就是说1秒钟能转120次,旋转延迟就是1/120/2 = 4.17ms;传输时间指的是从磁盘读出或将数据写入磁盘的时间,一般在零点几毫秒,相对于前两个时间可以忽略不计。那么访问一次磁盘的时间,即一次磁盘IO的时间约等于5+4.17 = 9ms左右,听起来还挺不错的,但要知道一台500 -MIPS的机器每秒可以执行5亿条指令,因为指令依靠的是电的性质,换句话说执行一次IO的时间可以执行40万条指令,数据库动辄十万百万乃至千万级数据,每次9毫秒的时间,显然是个灾难。
考虑到磁盘IO是非常高昂的操作,计算机操作系统做了一些优化,当一次IO时,不光把当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区内,因为局部预读性原理告诉我们,当计算机访问一个地址的数据的时候,与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关,一般为4k或8k,也就是我们读取一页内的数据时候,实际上才发生了一次IO,这个理论对于索引的数据结构设计非常有帮助。
事实1 : 不同容量的存储器,访问速度差异悬殊。
磁盘(ms级别) << 内存(ns级别), 100000倍
若内存访问需要1s,则一次外存访问需要一天
为了避免1次外存访问,宁愿访问内存100次…所以将最常用
的数据存储在最快的存储器中事实2 : 从磁盘中读 1 B,与读写 1KB 的时间成本几乎一样
从以上数据中可以总结出一个道理,索引查询的数据主要受限于硬盘的I/O速度,查询I/O次数越少,速度越快,所以B树的结构才应需求而生;B树的每个节点的元素可以视为一次I/O读取,树的高度表示最多的I/O次数,在相同数量的总元素个数下,每个节点的元素个数越多,高度越低,查询所需的I/O次数越少;假设,一次硬盘一次I/O数据为8K,索引用int(4字节)类型数据建立,理论上一个节点最多可以为2000个元素,200020002000=8000000000,80亿条的数据只需3次I/O(理论值),可想而知,B树做为索引的查询效率有多高;另外也可以看出同样的总元素个数,查询效率和树的高度密切相关。
4 B+树与B树
4.1 B+ 树比B树更适合索引?
1)
B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了;
2)
B+树查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当;
3)
B+树便于范围查询(最重要的原因,范围查找是数据库的常态)
B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作或者说效率太低。
补充:B树的范围查找用的是中序遍历,而B+树用的是在链表上遍历。
4.2 MySQL中InnoDB与MyISAM中采用B+树结构?
(1)B+树
(2)InnoDB
(3)MyISAM
-
B树和B+树的区别
2021-09-14 11:51:56文章目录简述写在前面1、B树2、B+树深入浅出B树B树深入B-树的查找B+ 树B+树概述B-树和B+树的区别拓展:MySQL为什么使用B-Tree(B+Tree)&& 存储知识存储数据最小单元主存存取原理磁盘存取原理总结 简述 写在...文章目录
简述
写在前面
大家在面试的时候,肯定都会被问到MySql的知识,以下是面试场景:
B树 和B+树是 MySQL索引使用的数据结构,对于索引优化和原理理解都非常重要,下面我的写文章就是要把B树,B+树的神秘面纱揭开,让大家在面试的时候碰到这个知识点一往无前,不再成为你的知识盲点!1、B树
- 这里的 B 是 Balance(平衡)的缩写。它是一种多路的平衡搜索树。
- 它跟普通的平衡二叉树的不同是,B树的每个节点可以存储多个数据,而且每个节点不止有两个子节点,最多可以有上千个子节点。
- B树中每个节点都存放着索引和数据,数据遍布整个树结构,搜索可能在非叶子节点结束,最好的情况是O(1)。
- 一般一棵 B 树的高度在 3 层左右,3 层就可满足 百万级别的数据量
B树 每个节点都存储了一定的范围区间,区间更多的情况下,搜索也就更快。
比如普通的二叉树对于 1~ 100 的索引值,首先分为 1~ 50 和51~ 100 两部分。
而 B树可以分为四个区间 1~ 25, 26~ 50, 51~ 75, 76~ 100 。甚至可以划分为更多区间,这样一次就能排除四分之三的数据
2、B+树
B+树是B树的一种变种,它与 B树 的 区别 是:
- 叶子节点保存了完整的索引和数据,而非叶子节点只保存索引值,因此它的查询时间固定为 log(n).
- 叶子节点中有指向下一个叶子节点的指针,叶子节点类似于一个单链表
- 正因为叶子节点保存了完整的数据以及有指针作为连接,B+树可以增加了区间访问性,提高了范围查询,而B树的范围查询相对较差
- B+树更适合外部存储。因为它的非叶子节点不存储数据,只保存索引。
B+树的示意图如下:
到此为止相信你已经对B树和B+树有一定认识,下面结合数据库深入了解
深入浅出
B树
B-树有如下特点:
- 所有键值分布在整颗树中(索引值和具体data都在每个节点里);
- 任何一个关键字出现且只出现在一个结点中;
- 搜索有可能在非叶子结点结束(最好情况O(1)就能找到数据);
- 在关键字全集内做一次查找,性能逼近二分查找;
B树深入
B树由来
定义:B-树是一类树,包括B-树、B+树、B*树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。
B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。定义只需要知道B-树允许每个节点有更多的子节点即可(多叉树)。子节点数量一般在上千,具体数量依赖外部存储器的特性。
先来看看为什么会出现B-树这类数据结构。
传统用来搜索的平衡二叉树有很多,如 AVL 树,红黑树等。这些树在一般情况下查询性能非常好,但当数据非常大的时候它们就无能为力了。原因当数据量非常大时,内存不够用,大部分数据只能存放在磁盘上,只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns,而磁盘在 10 ms 左右。速度相差了近 5 个数量级,磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能?减少磁盘 IO 次数,像 AVL 树,红黑树这类平衡二叉树从设计上无法“迎合”磁盘。
上图是一颗简单的平衡二叉树,平衡二叉树是通过旋转来保持平衡的,而旋转是对整棵树的操作,若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log n(底数为2),这样逻辑上很近的节点实际可能非常远,无法很好的利用磁盘预读(局部性原理),所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。
我们从“迎合”磁盘的角度来看看B-树的设计。
索引的效率依赖与磁盘 IO 的次数,快速索引需要有效的减少磁盘 IO 次数,如何快速索引呢?索引的原理其实是不断的缩小查找范围,就如我们平时用字典查单词一样,先找首字母缩小范围,再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快,B-树每次将范围分割为多个区间,区间越多,定位数据越快越精确。那么如果节点为区间范围,每个节点就较大了。所以新建节点时,直接申请页大小的空间(磁盘存储单位是按 block 分的,一般为 512 Byte。磁盘 IO 一次读取若干个 block,我们称为一页,具体大小和操作系统有关,一般为 4 k,8 k或 16 k),计算机内存分配是按页对齐的,这样就实现了一个节点只需要一次 IO。
上图是一棵简化的B-树,多叉的好处非常明显,有效的降低了B-树的高度,为底数很大的 log n,底数大小与节点的子节点数目有关,一般一棵B-树的高度在 3 层左右。层数低,每个节点区确定的范围更精确,范围缩小的速度越快(比二叉树深层次的搜索肯定快很多)。上面说了一个节点需要进行一次 IO,那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an),并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。点评:B树的每个节点,都是存多个值的,不像二叉树那样,一个节点就一个值,B树把每个节点都给了一点的范围区间,区间更多的情况下,搜索也就更快了,比如:有1-100个数,二叉树一次只能分两个范围,0-50和51-100,而B树,分成4个范围 1-25, 25-50,51-75,76-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的
B-树的查找
我们来看看B-树的查找,假设每个节点有 n 个 key值,被分割为 n+1 个区间,注意,每个 key 值紧跟着 data 域,这说明B-树的 key 和 data 是聚合在一起的。一般而言,根节点都在内存中,B-树以每个节点为一次磁盘 IO,比如上图中,若搜索 key 为 25 节点的 data,首先在根节点进行二分查找(因为 keys 有序,二分最快),判断 key 25 小于 key 50,所以定位到最左侧的节点,此时进行一次磁盘 IO,将该节点从磁盘读入内存,接着继续进行上述过程,直到找到该 key 为止。
Data* BTreeSearch(Root *node, Key key) { Data* data; if(root == NULL) return NULL; data = BinarySearch(node); if(data->key == key) { return data; }else{ node = ReadDisk(data->next); BTreeSearch(node, key); } }
B+ 树
B+树概述
B+树是B-树的变体,也是一种多路搜索树, 它与 B- 树的不同之处在于:
- 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
- 为所有叶子结点增加了一个链指针
简化 B+树 如下图
因为内节点并不存储 data,所以一般B+树的叶节点和内节点大小不同,而B-树的每个节点大小一般是相同的,为一页。为了增加 区间访问性,一般会对B+树做一些优化。
如下图带顺序访问的B+树。B-树和B+树的区别
1.B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。
如下所示B-树/B+树查询节点 key 为 50 的 data。
B-树:
从上图可以看出,key 为 50 的节点就在第一层,B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。B+树:
由于B+树所有的 data 域都在根节点,所以查询 key 为 50的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)。点评:B树的由于每个节点都有key和data,所以查询的时候可能不需要O(logn)的复杂度,甚至最好的情况是O(1)就可以找到数据,而B+树由于只有叶子节点保存了data,所以必须经历O(logn)复杂度才能找到数据
2. B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。
根据空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。B+树可以很好的利用局部性原理,若我们访问节点 key为 50,则 key 为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数。
当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。点评:由于B+树的叶子节点的数据都是使用链表连接起来的,而且他们在磁盘里是顺序存储的,所以当读到某个值的时候,磁盘预读原理就会提前把这些数据都读进内存,使得范围查询和排序都很快
3.B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确
这个很好理解,由于B-树节点内部每个 key 都带着 data 域,而B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的,一次磁盘 IO 会读取若干个 block,具体和操作系统有关,那么由于磁盘 IO 数据大小是固定的,在一次 IO 中,单个元素越小,量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树,从这点来看B+树相对B-树磁盘 IO 次数少。
点评:由于B树的节点都存了key和data,而B+树只有叶子节点存data,非叶子节点都只是索引值,没有实际的数据,这就时B+树在一次IO里面,能读出的索引值更多。从而减少查询时候需要的IO次数!
从上图可以看出相同大小的区域,B-树仅有 2 个 key,而B+树有 3 个 key。拓展:MySQL为什么使用B-Tree(B+Tree)&& 存储知识
上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。
一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。
存储数据最小单元
我们都知道计算机在存储数据的时候,有最小存储单元,这就好比我们今天进行现金的流通最小单位是一毛。
在计算机中磁盘存储数据最小单元是扇区,一个扇区的大小是512字节,而文件系统(例如XFS/EXT4)他的最小单元是块,一个块的大小是4k
而对于我们的InnoDB存储引擎也有自己的最小储存单元——页(Page),一个页的大小是16K。
下面几张图可以帮你理解最小存储单元:
文件系统中一个文件大小只有1个字节,但不得不占磁盘上4KB的空间。
磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。
在MySQL中我们的InnoDB页的大小默认是16k,当然也可以通过参数设置:
数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢?假设一行数据的大小是1k,那么一个页可以存放16行这样的数据。主存存取原理
目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。
从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。主存的存取过程如下:
当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。
写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。
这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。
磁盘存取原理
上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。
图6是磁盘的整体结构示意图。
一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。
图7是磁盘结构的示意图。
盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。
局部性原理与磁盘预读
由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:
当一个数据被用到时,其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。
预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。
所以IO一次就是读一页的大小
总结
MySQL的B树和B+树原理就说到这里了。
我是JavaPub,下期见
参考:https://www.cnblogs.com/gslgb/p/14821363.html
-
B树
2019-04-30 11:15:19注意:首先需要说明的一点是:B-树就是B树,没有所谓的B减树 维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找...注意:首先需要说明的一点是:B-树就是B树,没有所谓的B减树
维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统。”
定义
B 树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。
- 根节点至少有两个子节点
- 每个节点有M-1个key,并且以升序排列
- 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
- 其它节点至少有M/2个子节点
下图是一个M=4 阶的B树:
可以看到B树是2-3树的一种扩展,他允许一个节点有多于2个的元素。
B树的插入及平衡化操作和2-3树很相似,这里就不介绍了。下面是往B树中依次插入
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
的演示动画:
B+树是对B树的一种变形树,它与B树的差异在于:
- 有k个子结点的结点必然有k个关键码;
- 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
- 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。
如下图,是一个B+树:
下图是B+树的插入动画:
B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。
B+ 树的优点在于:
- 由于B+树在内部节点上不包含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
- B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。
但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。下面是B 树和B+树的区别图:
分析
对B树和B+树的分析和对前面讲解的2-3树的分析类似,
对于一颗节点为N度为M的子树,查找和插入需要logM-1N ~ logM/2N次比较。这个很好证明,对于度为M的B树,每一个节点的子节点个数为M/2 到 M-1之间,所以树的高度在logM-1N至logM/2N之间。
这种效率是很高的,对于N=62*1000000000个节点,如果度为1024,则logM/2N <=4,即在620亿个元素中,如果这棵树的度为1024,则只需要小于4次即可定位到该节点,然后再采用二分查找即可找到要找的值
引言
我们都知道二叉查找树的查找的时间复杂度是O(log N),其查找效率已经足够高了,那为什么还有B树和B+树的出现呢?难道它两的时间复杂度比二叉查找树还小吗?
答案当然不是,B树和B+树的出现是因为另外一个问题,那就是磁盘IO;众所周知,IO操作的效率很低,那么,当在大量数据存储中,查询时我们不能一下子将所有数据加载到内存中,只能逐一加载磁盘页,每个磁盘页对应树的节点。造成大量磁盘IO操作(最坏情况下为树的高度)。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁,进而导致效率低下。
所以,我们为了减少磁盘IO的次数,就你必须降低树的深度,将“瘦高”的树变得“矮胖”。一个基本的想法就是:
(1)、每个节点存储多个元素
(2)、摒弃二叉树结构,采用多叉树这样就引出来了一个新的查找树结构 ——多路查找树。 根据AVL给我们的启发,一颗平衡多路查找树(B~树)自然可以使得数据的查找效率保证在O(logN)这样的对数级别上。
下面来具体介绍一下B树(Balance Tree),
B树一个m阶的B树具有如下几个特征:B树中所有结点的孩子结点最大值称为B树的阶,通常用m表示。一个结点有k个孩子时,必有k-1个关键字才能将子树中所有关键字划分为k个子集。
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子,其中 ceil(m/2) ≤ k ≤ m
3.每一个叶子节点都包含k-1个元素,其中 ceil(m/2) ≤ k ≤ m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域划分
6.每个结点的结构为:(n,A0,K1,A1,K2,A2,… ,Kn,An)
其中,Ki(1≤i≤n)为关键字,且Ki<Ki+1(1≤i≤n-1)。
Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。
n为结点中关键字的个数,满足ceil(m/2)-1≤n≤m-1。示例:三阶B树(实际中节点中元素很多)
这里写图片描述
查询以上图为例:若查询的数值为5:
第一次磁盘IO:在内存中定位(与17、35比较),比17小,左子树;
第二次磁盘IO:在内存中定位(与8、12比较),比8小,左子树;
第三次磁盘IO:在内存中定位(与3、5比较),找到5,终止。
整个过程中,我们可以看出:比较的次数并不比二叉查找树少,尤其适当某一节点中的数据很多时,但是磁盘IO的次数却是大大减少。比较是在内存中进行的,相比于磁盘IO的速度,比较的耗时几乎可以忽略。所以当树的高度足够低的话,就可以极大的提高效率。相比之下,节点中的元素多点也没关系,仅仅是多了几次内存交互而已,只要不超过磁盘页的大小即可。
插入对高度为k的m阶B树,新结点一般是插在叶子层。通过检索可以确定关键码应插入的结点位置。然后分两种情况讨论:
1、 若该结点中关键码个数小于m-1,则直接插入即可。
2、 若该结点中关键码个数等于m-1,则将引起结点的分裂。以中间关键码为界将结点一分为二,产生一个新结点,并把中间关键码插入到父结点(k-1层)中
重复上述工作,最坏情况一直分裂到根结点,建立一个新的根结点,整个B树增加一层。例如:在下面的B树中插入key:4
这里写图片描述
第一步:检索key插入的节点位置如上图所示,在3,5之间;
第二步:判断节点中的关键码个数:
节点3,5已经是两元素节点,无法再增加。父亲节点 2, 6 也是两元素节点,也无法再增加。根节点9是单元素节点,可以升级为两元素节点。;第三步:结点分裂:
拆分节点3,5与节点2,6,让根节点9升级为两元素节点4,9。节点6独立为根节点的第二个孩子。最终结果如下图:虽然插入比较麻烦,但是这也能确保B树是一个自平衡的树
这里写图片描述
删除B树中关键字的删除比插入更复杂,在这里,只介绍其中的一种方法:
在B树上删除关键字k的过程分两步完成:
(1)找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。
(2)若该结点为非叶结点,且被删关键字为该结点中第i个关键字key[i],则可从指针son[i]所指的子树中
找出最小关键字Y,代替key[i]的位置,然后在叶结点中删去Y。因此,把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。
在B-树叶结点上删除一个关键字的方法:
首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理,共有三种可能情况:(1)如果被删关键字所在结点的原关键字个数n>=ceil(m/2),说明删去该关键字后该结点仍满足B树的定义。
这种情况最为简单,只需从该结点中直接删去关键字即可。(2)如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1,说明删去该关键字后该结点将不满足B树的定义,
需要调整。调整过程为:
如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右(左)兄弟结点中的关键字数目大于
ceil(m/2)-1。则可将右(左)兄弟结点中最小(大)关键字上移至双亲结点。而将双亲结点中小(大)于该上
移关键字的关键字下移至被删关键字所在结点中。
如果左右兄弟结点中没有“多余”的关键字,即与该结点相邻的右(左)兄弟结点中的关键字数目均等于
ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左(或右)兄弟结点以及双亲结点中分割二者
的关键字合并成一个结点,即在删除关键字后,该结点中剩余的关键字加指针,加上双亲结点中的关键字Ki一起,
合并到Ai(是双亲结点指向该删除关键字结点的左(右)兄弟结点的指针)所指的兄弟结点中去。如果因此使双亲
结点中关键字个数小于ceil(m/2)-1,则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使
整个树减少一层。总之,设所删关键字为非终端结点中的Ki,则可以指针Ai所指子树中的最小关键字Y代替Ki,然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。
下面举一个简单的例子:删除元素11.
这里写图片描述第一步:判断该元素是否在叶子结点上。
该元素在叶子节点上,可以直接删去,但是删除之后,中间节点12只有一个孩子,不符合B树的定义:每个中间节点都包含k个孩子,(其中 ceil(m/2) <= k <= m)所以需要调整;第二步:判断其左右兄弟结点中有“多余”的关键字,即:原关键字个数n>=ceil(m/2) - 1;
显然结点11的右兄弟节点中有多余的关键字。那么可将右兄弟结点中最小关键字上移至双亲结点。而将双亲结点中小于该上移关键字的关键字下移至被删关键字所在结点中即可这里写图片描述
注意①、B树主要用于文件系统以及部分数据库索引,例如: MongoDB。而大部分关系数据库则使用B+树做索引,例如:mysql数据库;
②、从查找效率考虑一般要求B树的阶数m >= 3;
③、B-树上算法的执行时间主要由读、写磁盘的次数来决定,故一次I/O操作应读写尽可能多的信息。因此B-树的结点规模一般以一个磁盘页为单位。一个结点包含的关键字及其孩子个数取决于磁盘页的大小。
B+ 树B+树是B树的变种,有着比B树更高的查询效率。下面,我们就来看看B+树和B树有什么不同
特点一个m阶的B+树具有如下几个特征:
1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据
都保存在叶子节点。2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小
自小而大顺序链接。3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。
下面是一棵3阶的B+树:
这里写图片描述
B+树通常有两个指针,一个指向根结点,另一个指向关键字最小的叶子结点。因些,对于B+树进行查找两种运算:一种是从最小关键字起顺序查找,另一种是从根结点开始,进行随机查找。
查找B+树的优势在于查找效率上,下面我们做一具体说明:
首先,B+树的查找和B树一样,类似于二叉查找树。起始于根节点,自顶向下遍历树,选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。
(1)、不同的是,B+树中间节点没有卫星数据(索引元素所指向的数据记录),只有索引,而B树每个结点中的每个关键字都有卫星数据;这就意味着同样的大小的磁盘页可以容纳更多节点元素,在相同的数据量下,B+树更加“矮胖”,IO操作更少
B树的卫星数据:
这里写图片描述
B+树的卫星数据:
这里写图片描述
需要补充的是,在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针。(2)、其次,因为卫星数据的不同,导致查询过程也不同;B树的查找只需找到匹配元素即可,最好情况下查找到根节点,最坏情况下查找到叶子结点,所说性能很不稳定,而B+树每次必须查找到叶子结点,性能稳定
(3)、在范围查询方面,B+树的优势更加明显
B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限,在不断通过中序遍历,知道查找到范围的上限即可。整个过程比较耗时。
而B+树的范围查找则简单了许多。首先通过二分查找,找到范围下限,然后同过叶子结点的链表顺序遍历,直至找到上限即可,整个过程简单许多,效率也比较高。
例如:同样查找范围[3-11],两者的查询过程如下:
B树的查找过程:
这里写图片描述
B+树的查找过程:
这里写图片描述
插入B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行,如果叶结点中的关键码个数超过m,就必须分裂成关键码数目大致相同的两个结点,并保证上层结点中有这两个结点的最大关键码。
删除B+树中的关键码在叶结点层删除后,其在上层的复本可以保留,作为一个”分解关键码”存在,如果因为删除而造成结点中关键码数小于ceil(m/2),其处理过程与B-树的处理一样。在此,我就不多做介绍了。
总结B+树相比B树的优势:
1.单一节点存储更多的元素,使得查询的IO次数更少;
2.所有查询都要查找到叶子节点,查询性能稳定;
3.所有叶子节点形成有序链表,便于范围查询。
---------------------
原文:https://blog.csdn.net/z_ryan/article/details/79685072
-
B树、B+树详解
2020-08-17 12:41:41B-树,即为B树。因为B树的原英文名称为B-tree,目前理解B的意思为平衡。 概念 首先,B树不要和二叉树混淆,在计算机科学中,B树是一种自平衡树数据结构,它维护有序数据并允许以对数时间进行搜索,顺序访问,插入和... -
数据结构(三)、B树,B+树,B*树
2020-08-04 21:32:06对于数据量比较大的情况下,对导致二叉树结构的深度也随之变大造成磁盘IO读写频繁导致查询效率低下,因此大部分关系型数据库都使用本篇要介绍的B+Tree结构,要理解B+树,需要先理解B树,本篇也会一起介绍B*树。 -
B树与B+树的区别
2021-09-14 00:00:30文章目录一、使用B-树的好处二、B-树深入三、B-树的查找四、B+ 树五、B-树和B+树的区别①B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中... -
MySQL索引(B树、B+树)
2022-02-27 14:47:01目录简介索引结构(树)为什么用树,而不用哈希表BTree索引B+Tree索引聚簇索引与非聚簇索引 简介 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。可以得到索引的本质:索引是数据结构。... -
种树:二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林
2020-07-11 17:09:31构造二叉搜索树代码实现:平衡二叉搜索树(AVL树)什么是平衡二叉搜索树?AVL树的节点数据结构AVL树构造左旋右旋双旋转新增节点(背多分)LL(右旋)RR(左旋)LRRL插入节点 树,什么是树? 树是我们计算机中非常重要的... -
B树与B+树
2020-09-07 16:48:34一、B树 1.1 B树的定义 B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数,阶数表示了一个结点最多有多少个孩子结点,一般用字母m表示阶数。当m取2时,就是我们常见的二叉搜索树。 一颗m阶... -
B树B+树面试
2019-12-17 11:27:12b树和b+树的区别 基本知识 2-3树 2-3-4树 B树存储引擎 (小知识点) (数据结构) B-树 简介 查找 插入 没有破坏结构 结构破坏 删除 终端 非终端 B+树 B树和二叉查找树的性能对比? 为什么数据库... -
一文彻底搞懂MySQL基础:B树和B+树的区别
2020-06-24 11:27:27B树和B+树是MySQL索引使用的数据结构,对于索引优化和原理理解都非常重要,下面我的写文章就是要把B树,B+树的神秘面纱揭开,让大家在面试的时候碰到这个知识点一往无前,不再成为你的知识盲点! 欢迎关注公 -
B树(B-树 B_树)、B+树、B*树
2019-06-26 15:11:56B树 B-tree树即B树,B即Balanced,平衡的意思。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是另一... -
B树和B+树区别
2020-07-14 11:13:21一,b树 b树(balance tree)和b+树应用在数据库索引,可以认为是m叉的多路平衡查找树,但是从理论上讲,二叉树查找速度和比较次数都是最小的,为什么不用二叉树呢? 因为我们要考虑磁盘IO的影响,它相对于内存来说... -
B树和B+树
2019-05-29 16:07:34一、B树和B+树的区别: B+树和B树相比,主要的不同点在以下3项: 所有关键码都存放在叶节点中,上层的非叶节点的关键码是其子树中最小(或最大)关键码的复写 叶节点包含了全部关键码及指向相应数据记录存放地址... -
简单剖析B树(B-Tree)与B+树
2018-03-25 11:30:09注意:首先需要说明的一点是:B-树就是B树,没有所谓的B减树 引言 我们都知道二叉查找树的查找的时间复杂度是O(log N),其查找效率已经足够高了,那为什么还有B树和B+树的出现呢?难道它两的时间复杂度比... -
平衡二叉树、B树、B+树,B*树的区别与联系
2019-05-29 11:20:34特点:平衡二叉树是采用二分法思想把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大的提升了数据检索的速度;平衡二叉树的数据结构组装过程遵循以下规则: (1)非叶子节点只能... -
二叉树 红黑树 B树 B+树的优缺点
2021-04-09 09:47:58本文将从最普通的二叉查找树开始,逐步说明各种树解决的问题以及面临的新问题,从而说明MySQL为什么选择B+树作为索引结构。 一、二叉查找树(BST):不平衡 二叉查找树(BST,Binary Search Tree),也叫二叉排序树,... -
B树、B+树
2019-03-26 15:40:08B树与B+树的区别在于: 1)在B+树中,具有n个关键字的节点只含有n棵子树,即每个关键字对应一颗子树;而在B树中,具有n个关键字的节点有n+1棵子树 2)B+树:每个节点(非根节点)关键字个数【m/2】<=n<=m (根... -
B树和B+树的查找方式及原因
2022-03-11 08:47:50B树支持随机查找 B+树支持随机查找和顺序查找 先把结论放上 B树仅支持随机查找 B+树支持随机查找和顺序查找 大致定义 至于B树和B+树的定义我就不展开了,随便找了两张图大家能有个大致的印象就行了 学习... -
红黑树与B树、B+树
2021-04-01 11:13:41一、红黑树 1、红黑树的特性 (1)每个节点或者是黑色,或者是红色。 (2)根节点是黑色。 (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!] (4)如果一个节点是红色的,... -
关于B树 B+树 B*树以及红黑树的理解
2019-02-21 19:34:321、首先要明白为什么有了AVL树之后还会出现这么多树的变种? 可以参考这个知乎有关几种树的应用的回答: 作者:王伟豪 链接:https://www.zhihu.com/question/30527705/answer/52919336 来源:知乎 AVL树:平衡... -
彻底理解B树
2021-04-14 22:32:03最近我们的项目使用到MongoDB,因为之前的数据存储都是选择MySql或者PostgressSQL,为什么...进一步了解到原来MongoDB的默认存储引擎是WridedTiger,并使用B树作为索引底层的数据结构。本着好奇最后打算对B树进行深入了解 -
高级数据结构之B树(B-tree)
2019-05-09 11:53:51一、B树(B-tree)的定义 B树是二叉树的一种推广,它在以硬盘为主的多级存储结构中常常被用来执行高效搜索。下图是一棵B树的简单示例,其中存储的是英语中的辅音字母。如果B树的一个内部结点x包含有x.n个关键字,... -
B树、B-树、B+树、B*树之间的关系
2018-07-17 21:30:20B树 B-tree树即B树,B即Balanced,平衡的意思。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是另... -
高薪程序员&面试题精讲系列54之你熟悉B树吗?有哪几种B树?
2022-01-11 10:02:43一. 面试题及剖析 ...但在之前的章节中,我并没有给大家介绍B树,所以今天 壹哥 专门给大家介绍一下什么是B树。emm,这个树的名字,听着总是怪怪的,不大正经的样子...... 那我们为什么非要掌握B树这棵“怪树