网站建设要哪些人,深圳做网站服务,商城系统开源,北京朝阳区邮编B树是一种树状数据结构#xff0c;它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。
1、B树的特性
B树中允许一个结点中包含多个key#xff0c;可以是3个、4个、5个甚至更多#xff0c;并不确定#xff0c;需要看具体的实… B树是一种树状数据结构它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。
1、B树的特性
B树中允许一个结点中包含多个key可以是3个、4个、5个甚至更多并不确定需要看具体的实现。现在我们选 择一个参数M来构造一个B树我们可以把它称作是M阶的B树那么该树会具有如下特点
每个结点最多有M-1个key并且以升序排列每个结点最多能有M个子结点根结点至少有两个子结点 在实际应用中B树的阶数一般都比较大通常大于100所以即使存储大量的数据B树的高度仍然比较小这 样在某些应用场景下就可以体现出它的优势。
2、B树存储数据
若参数M选择为5那么每个结点最多包含4个键值对我们以5阶B树为例看看B树的数据存储。 3、B树在磁盘文件中的应用
在我们的程序中不可避免的需要通过IO操作文件而我们的文件是存储在磁盘上的。计算机操作磁盘上的文件是通过文件系统进行操作的在文件系统中就使用到了B树这种数据结构。
3.1、磁盘
磁盘能够保存大量的数据从GB一直到TB级但是 他的读取速度比较慢因为涉及到机器操作读取速度为毫秒 级 。 磁盘由盘片构成,每个盘片有两面又称为盘面 。盘片中央有一个可以旋转的主轴他使得盘片以固定的旋转速率 旋转通常是5400rpm或者是7200rpm,一个磁盘中包含了多个这样的盘片并封装在一个密封的容器内 。盘片的每个表面是由一组称为磁道同心圆组成的 每个磁道被划分为了一组扇区 每个扇区包含相等数量的数据位通常是512个子节扇区之间由一些间隙隔开,这些间隙中不存储数据 。
3.2、磁盘IO 磁盘用磁头来读写存储在盘片表面的位而磁头连接到一个移动臂上移动臂沿着盘片半径前后移动可以将磁头 定位到任何磁道上这称之为寻道操作。一旦定位到磁道后盘片转动磁道上的每个位经过磁头时读写磁头就 可以感知到该位的值也可以修改值。对磁盘的访问时间分为 寻道时间旋转时间以及传送时间。 由于存储介质的特性磁盘本身存取就比主存慢很多再加上机械运动耗费因此为了提高效率要尽量减少磁盘I/O减少读写操作。 为了达到这个目的磁盘往往不是严格按需读取而是每次都会预读即使只需要一个字节磁盘也会从这个位置开始顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理当一个数据被用到时其附近的数据也通常会马上被使用。由于磁盘顺序读取的效率很高不需要寻道时间只需很少的旋转时间因此预读可以提高I/O效率。 页是计算机管理存储器的逻辑块硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块每个存储 块称为一页1024个字节或其整数倍预读的长度一般为页的整倍数。主存和磁盘以页为单位交换数据。当程 序要读取的数据不在主存中时会触发一个缺页异常此时系统会向磁盘发出读盘信号磁盘会找到数据的起始位 置并向后连续读取一页或几页载入内存中然后异常返回程序继续运行。 文件系统的设计者利用了磁盘预读原理将一个结点的大小设为等于一个页1024个字节或其整数倍这样每 个结点只需要一次I/O就可以完全载入。那么3层的B树可以容纳1024*1024*1024差不多10亿个数据如果换成二 叉查找树则需要30层假定操作系统一次读取一个节点并且根节点保留在内存中那么B树在10亿个数据中查 找目标值只需要小于3次硬盘读取就可以找到目标值但红黑树需要小于30次因此B树大大提高了IO的操作效率。
4、B树
B树是对B树的一种变形树它与B树的差异在于
1. 非叶结点仅具有索引作用也就是说非叶子结点只存储key不存储value
2. 树的所有叶结点构成一个有序链表可以按照key排序的次序遍历全部数据。
4.1 B树存储数据
若参数M选择为5那么每个结点最多包含4个键值对我们以5阶B树为例看看B树的数据存储。
4.2 B树和B树的对比
B 树的优点在于
1.由于B树在非叶子结点上不包含真正的数据只当做索引使用因此在内存相同的情况下能够存放更多的key。 2.B树的叶子结点都是相连的因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。
B树的优点在于
由于B树的每一个节点都包含key和value因此我们根据key查找value时只需要找到key所在的位置就能找到 value但B树只有叶子结点存储数据索引每一次查找都必须一次一次一直找到树的最大深度处也就是叶 子结点的深度才能找到value。
B树在数据库中的应用
在数据库的操作中查询操作可以说是最频繁的一种操作因此在设计数据库时必须要考虑到查询的效率问题 在很多数据库中都是用到了B树来提高查询的效率
在操作数据库时我们为了提高查询效率可以基于某张表的某个字段建立索引就可以提高查询效率那其实这 个索引就是B树这种数据结构实现的。 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 k8 k或 16 k计算机内存分配是按页对齐的这样就实现了一个节点只需要一次 IO。 上图是一棵简化的B-树多叉的好处非常明显有效的降低了B-树的高度为底数很大的 log n底数大小与节点的子节点数目有关一般一棵B-树的高度在 3 层左右。层数低每个节点区确定的范围更精确范围缩小的速度越快比二叉树深层次的搜索肯定快很多。上面说了一个节点需要进行一次 IO那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an)并将该节点的子节点分割成 n1 个区间来进行索引(X1 a1, a2 X2 a3, … , an1 Xn anXn1 an)。
点评B树的每个节点都是存多个值的不像二叉树那样一个节点就一个值B树把每个节点都给了一点的范围区间区间更多的情况下搜索也就更快了比如有1-100个数二叉树一次只能分两个范围0-50和51-100而B树分成4个范围 1-25 25-5051-7576-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的
三、B-树的查找 我们来看看B-树的查找假设每个节点有 n 个 key值被分割为 n1 个区间注意每个 key 值紧跟着 data 域这说明B-树的 key 和 data 是聚合在一起的。一般而言根节点都在内存中B-树以每个节点为一次磁盘 IO。
比如上图中若搜索 key 为 25 节点的 data首先在根节点进行二分查找因为 keys 有序二分最快判断 key 25 小于 key 50所以定位到最左侧的节点此时进行一次磁盘 IO将该节点从磁盘读入内存接着继续进行上述过程直到找到该 key 为止。
B 树 B树是B-树的变体也是一种多路搜索树, 它与 B- 树的不同之处在于:
所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)。 为所有叶子结点增加了一个链指针。
简化 B树 如下图 因为内节点并不存储 data所以一般B树的叶节点和内节点大小不同而B-树的每个节点大小一般是相同的为一页。 使用B树的好处 由于B树的内部节点只存放键不存放值因此一次读取可以在内存页中获取更多的键有利于更快地缩小查找范围。
B树的叶节点由一条链相连因此当需要进行一次全数据遍历的时候B树只需要使用O(logN)时间找到最小的一个节点然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历这会需要更多的内存置换次数因此也就需要花费更多的时间 知识来源
【23版面试突击】你知道B树和B树的区别吗MySQL为什么使用B树而不是B树_哔哩哔哩_bilibili
Java数据结构算法B树和B树 - 知乎
B树与B树的区别_b树和b树的区别_森明帮大于黑虎帮的博客-CSDN博客
