PHP数据结构(十九) ——B+树

PHP数据结构(十九)——B+树

(原创内容,转载请注明来源,谢谢)

一、概述

B+树是B树的变种,在数据库系统、文件系统等方面,B+树的运用非常广泛。

1、B+树的要求

1)有n棵子树的结点中含有n个关键字。(B树是n-1个关键字。)

2)所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。这点意味着,叶子节点存在指向相邻叶子节点的指针。这个是在树形的数据结构中非常特殊的地方,使得B+树的数据结构看起来有点像图的数据结构了。(B树的叶子节点没有保存父节点的信息,因此并没有包括全部需要查找的信息。)

3)所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。(B 树的非终节点也包含需要查找的有效信息,但是不包含和子节点相同的关键字。)

2、B+树如下图所示(图片来自网络)

3、B+树的特性

1)所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的。

2)B+树比较稳定,查询过程不可能在非叶子节点命中。

3)非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层。

4、增删改查

1)查找

B+树的查找和B树几乎一样。主要区别:

a.前面一直提到的,查找结束一定是在叶子节点,无论是否查找。但是有一个例外,当B+树的父节点的关键字数组都是存储子节点中关键字最小的值时,如果待查的关键字小于根节点的最小的值,则停止查找。因为此值已经表示整个树最小的值。因此,可以过滤掉很多无用的查找。

b.当要进行范围查找时,只需要查找最小以及最大的节点所在的位置,然后比较在此之间的各关键字即可。这是因为B+树的叶子节点之间有指针相连。

2)插入

B+树的插入,和B树不太一样,步骤如下(假设B+树的父节点是存储子节点中最小的关键字):

a.在B+树中查找,如果关键字存在,插入失败。否则,插入在最后查找的那个叶子节点中,并且保证插入后节点的关键字仍是有序的。

下列a、b、c只会发生一种,且前提是B+树的父节点是存储子节点中最小的关键字,如果存储的是最大的关键字,则相似,不再进行赘述。

b.如果插入后,叶子节点关键字的个数满足小于m(m是父节点子树的个数),且元素大于父节点指向该元素的关键字,则插入完毕。

c.如果插入后,叶子节点关键字的个数满足小于m,且元素小于父节点指向该元素的关键字,则更新父节点的关键字为刚刚插入的这个关键字,插入完毕。

d.如果插入后,叶子节点关键字的个数满足大于m,则需要分裂叶子节点,将叶子节点按关键字的大小顺序,分裂成两个叶子节点,每个叶子节点含有的关键字数量相同。并根据分裂后的叶子节点,更新父节点指向该叶子节点的关键字。

如果父节点也超出要求,则继续分裂。如果父节点是根节点,则B+树插入后多一层。

3)删除

B+树的删除,也和B树不太一样,步骤如下(假设B+树的父节点是存储子节点中最小的关键字):

a.在B+树中查找,如果关键字不存在,删除失败。否则,在叶子节点中删除该关键字。

下列b、c、d、e只会发生一种,且前提是B+树的父节点是存储子节点中最小的关键字,如果存储的是最大的关键字,则相似,不再进行赘述。

b.如果删除后,叶子节点关键字的个数满足大于m/2-1(m/2的结果取进一法,m是父节点子树的个数),且被删除的元素不在父节点中,则删除完毕。

c.如果删除后,叶子节点关键字的个数满足大于m/2-1,且被删除的元素在父节点中,则需要重新取被删除关键字的节点中最小的关键字,替换父节点中指向该节点的关键字。

d.如果删除后,叶子节点关键字的个数小于m/2-1,且左右相邻兄弟节点至少有一个兄弟节点满足元素个数大于m/2,则把相邻的兄弟中最小(或最大,左兄弟取最大,右兄弟取最小)的关键字移到刚刚被删除关键字的节点中,并且相应的修改父节点中的关键字的值。如果左右兄弟都满足迁移条件,则取关键字较多的那个兄弟进行迁移。

e.如果删除后,叶子节点关键字的个数小于m/2-1,且左右相邻兄弟节点都不满足元素个数大于m/2,则需要合并被删除的元素与左右兄弟节点中元素较少的节点。合并后,相应的要删除父节点的一个关键字。

如果父节点的关键字被删除后,不满足要求,则需要与相邻的父节点中的关键字较少的那一个节点合并。最终有可能出现B+树少一层的情况。

二、文件和数据库的索引采用B+树的理由

1)文件与数据库都是需要较大的存储,且需要永久性存储,不能断电就消失,因此不可能存储在内存中,故要存储到磁盘上。因此就需要考虑磁盘I/O的问题。

2)考虑到I/O问题,则需要用B树或B树的相应变种来实现。

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

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

5)于B+树的叶子节点之间是有指针的,因此B+树只要遍历叶子节点就可以实现整棵树的遍历(B树需要采用中序遍历的方式才能获取整棵树)。特别是在数据库中基于范围的查询是非常频繁的情况下,可以通过定位一个节点的关键字,就可以利用叶子节点关键字之间的指针把剩余的符合要求的关键字全部取出。

三、B+树在Mysql数据库的应用

Mysql数据库的引擎,最常见的两个是InnoDB 与 MyISAM,其主要区别在于InnoDB支持行级锁、事务处理与外键,MyISAM支持表级锁且不支持事务与外键。MyISAM类型的表强调的是性能,执行速度比InnoDB快,读性能强,但是不支持高级操作,写性能不如InnoDB。具体这两个引擎的区别以后数据库的专题文章讲述,由于这两个引擎都是采用B+树的结构存储索引,因此这里主要讲这两个引擎对B+树应用的区别。

1、MyISAM

MyISAM引擎叶节点的关键字指定的值域存放的是数据记录的地址,不保存实际的数据。主索引和辅助索引都是这样,区别在于主索引要求每个字段唯一,辅助索引没有这个要求。

因此,MyISAM中索引检索的算法为首先按照B+树搜索算法搜索索引,如果指定的关键字存在,则取出其关键字指定的值,然后以关键字指定的值为地址,读取相应数据记录。

2、InnoDB

InnoDB表数据文件本身就是按B+树组织的一个索引结构,这棵树的叶节点关键字指定的值域保存了完整的数据记录。这个索引的关键字是数据表的主键,因此InnoDB表数据文件本身就是主索引。这种索引叫做聚集索引。

InnoDB的辅助索引是聚簇索引,也会包含主键列,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

3、区别

综上所述,区别在于以下几点:

1)主索引区别在于InnoDB的数据文件本身就是索引文件,MyISAM的索引和数据是分开的。

2)辅助索引区别在于InnoDB的辅助索引关键值指定的值域存储相应记录主键的值而不是地址, MyISAM的辅助索引和主索引几乎一样。

四、好的文章

http://blog.csdn.net/v_JULY_v/article/details/6530142/

http://www.cnblogs.com/xyxxs/p/4440187.html

——written by linhxx 2017.07.17

相关阅读:

PHP数据结构(十八) ——直接插入排序

PHP数据结构(十七) ——内部排序综述

PHP数据结构(十六) ——B树

PHP数据结构(十五) ——哈希表​

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-17

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

latex数学公式

923
来自专栏我是攻城师

Apache Pig学习笔记(二)

3259
来自专栏PHP技术

PHP字符串和数组操作

*字符串查找 $email = 'name@example@.com'; $domain = strstr($email, '@'); echo $do...

3064
来自专栏加米谷大数据

Hive内置运算符

Hive有四种类型的运算符: 关系运算符 算术运算符 逻辑运算符 复杂运算符 关系运算符 这些操作符被用来比较两个操作数。下表描述了在Hive中可用的关系运...

3156
来自专栏爱撒谎的男孩

MongoDB初级入门

{ "_id" : "Mary", "sum_age" : 75 } { "_id" : "Jack", "sum_age" : 66 } { "_id" : ...

1585
来自专栏Hadoop数据仓库

HAWQ技术解析(十) —— 过程语言

        HAWQ支持用户自定义函数(user-defined functions,UDF),还支持给HAWQ内部的函数起别名。编写UDF的语言可以是SQ...

3765
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高五】使用序列化实现对象的拷贝

【Java提高五】使用序列化实现对象拷贝 我们知道在Java中存在这个接口Cloneable,实现该接口的类都会具备被拷贝的能力,同时拷贝是在内存中进行,在性能...

3548
来自专栏哲学驱动设计

重构一个繁琐的数据结构

    在GIX4项目的开发过程中,遇到一个比较复杂的数据结构。复杂,是因为它有许多限制条件。我的工作是在现有系统中,添加新的功能,并在过程中重构部分旧代码。 ...

19010
来自专栏xcywt

《大话数据结构》 查找 以及一个简单的哈希表例子

第八章 查找 定义:查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。 8.2 查找概论 查找表(Search table):...

42512
来自专栏风口上的猪的文章

.NET面试题系列[10] - IEnumerable的派生类

IEnumerable分为两个版本:泛型的和非泛型的。IEnumerable只有一个方法GetEnumerator。如果你只需要数据而不打算修改它,不打算为集合...

572

扫描关注云+社区