除了 B+ 树,你可能还听说过 B 树、 B- 树,实际上, B- 树就是 B 树,英文翻译都是 B-Tree ,这里的 “-” 并不是相对 B+ 树中的 “+” ,而只是一个连接符。而 B 树实际上是低级版的B+ 树,或者说 B+ 树是 B 树的改进版。
B+ tree
B+ tree 实际上是一颗m叉平衡查找树(不是二叉树)
平衡查找树定义:树中任意一个节点的左右子树的高度相差不能大于 1
- /**
- * 这是B+树非叶子节点的定义。
- *
- * 假设keywords=[3, 5, 8, 10]
- * 4个键值将数据分为5个区间:(-INF,3), [3,5), [5,8), [8,10), [10,INF)
- * 5个区间分别对应:children[0]...children[4]
- *
- * m值是事先计算得到的,计算的依据是让所有信息的大小正好等于页的大小:
- * PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
- */
- public class BPlusTreeNode {
- // 5叉树
- public static int m = 5;
- // 键值,用来划分数据区间
- public int[] keywords = new int[m-1];
- // 保存子节点指针
- public BPlusTreeNode[] children = new BPlusTreeNode[m];
- }
- /**
- * 这是B+树中叶子节点的定义。
- *
- * B+树中的叶子节点跟内部结点是不一样的,
- * 叶子节点存储的是值,而非区间。
- * 这个定义里,每个叶子节点存储3个数据行的键值及地址信息。
- *
- * k值是事先计算得到的,计算的依据是让所有信息的大小正好等于页的大小:
- * PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
- */
- public class BPlusTreeLeafNode {
- public static int k = 3;
- // 数据的键值
- public int[] keywords = new int[k];
- // 数据地址
- public long[] dataAddress = new long[k];
- // 这个结点在链表中的前驱结点
- public BPlusTreeLeafNode prev;
- // 这个结点在链表中的后继结点
- public BPlusTreeLeafNode next;
- }
在B+ 树中,树中的节点并不存储数据本身,而是只是作为索引。除此之外,所有记录的节点按大小顺序存储在同一层的叶节点中,并且每个叶节点通过指针连接。
总结下,B+树有以下特点
这样设计还有以下优点:
B +树的非叶子节点仅存储键,占用很小的空间,因此节点的每一层可以索引的数据范围要宽得多。换句话说,可以为每个IO操作搜索更多数据
叶子节点成对连接,符合磁盘的预读特性。例如,叶节点存储50和55,它们具有指向叶节点60和62的指针。当我们从磁盘读取对应于50和55的数据时,由于磁盘的预读特性,我们将顺便提一下60和62。读出相应的数据。这次是顺序读取,而不是磁盘搜索,加快了速度。
支持范围查询,局部范围查询非常高效,每个节点都可以索引更大,更准确的范围,这意味着B +树单磁盘IO信息大于B树,并且I / O效率更高
由于数据存储在叶节点层中,并且有指向其他叶节点的指针,因此范围查询仅需要遍历叶节点层,而无需遍历整个树。
由于磁盘访问速度和内存之间存在差距,为了提高效率,应将磁盘I / O最小化。磁盘通常不是严格按需读取的,而是每次都被预读。磁盘读取所需的数据后,它将向后读取内存中的一定长度的数据。这样做的理论基础是计算机科学中众所周知的本地原理:
B-Tree
B-Tree实际上也是一颗m叉平衡查找树
B树和B+树之间的区别
为什么MongoDB使用B-Tree,Mysql使用B+Tree ?
B +树中的非叶子节点不存储数据,并且存储在叶节点中的所有数据使得查询时间复杂度固定为log n。B树查询时间复杂度不是固定的,它与键在树中的位置有关,最好是O(1)。
我们已经说过,尽可能少的磁盘IO是提高性能的有效方法。MongoDB是一个聚合数据库,而B树恰好是键域和数据域的集群。
至于为什么MongoDB使用B树而不是B +树,可以从其设计的角度考虑它。 MongoDB不是传统的关系数据库,而是以BSON格式(可以认为是JSON)存储的nosql。目的是高性能,高可用性和易于扩展。
Mysql是关系型数据库,最常用的是数据遍历操作(join),而MongoDB它的数据更多的是聚合过的数据,不像Mysql那样表之间的关系那么强烈,因此MongoDB更多的是单个查询。
由于Mysql使用B+树,数据在叶节点上,叶子节点之间又通过双向链表连接,更加有利于数据遍历,而MongoDB使用B树,所有节点都有一个数据字段。只要找到指定的索引,就可以对其进行访问。毫无疑问,单个查询MongoDB平均查询速度比Mysql快。
Hash索引
简而言之,哈希索引使用某种哈希算法将键值转换为新的哈希值。不需要像B +树那样从根节点到叶节点逐步搜索。只需要一种哈希算法,就可以立即找到对应的位置,速度非常快。(此处可以想想Java中的HashMap)。
B+树索引和Hash索引的区别
1.如果是等价查询,则哈希索引显然具有绝对优势,因为只需一种算法即可找到相应的键值;当然,前提是键值是唯一的,如果存在hash冲突就必须链表遍历了。
2.这样做虽然支持了范围查询但是时间复杂度是O(n),效率比跳表和B+Tree差
3.哈希索引无法使用索引排序以及模糊匹配
4..哈希索引也不支持多列联合索引的最左边匹配规则。
5.键值大量冲突的情况下,Hash索引效率极低
struts json 类型异常返回到js弹框问题解决办法 当struts 框架配置了异常时 例如...
下面是ajax代码和Controller层代码,期初以为是后台程序写错了。 $("#sourcefile...
文章目录 关系数据库 关系数据库简介 关系数据结构及形式化定义 关系 关系模式 ...
在 2021 年,人们喜欢 Linux 的理由比以往任何时候都多。在这个系列中,我将分享...
前言 我们在使用ajax异步的提交多选框得到需要操作的对象的id,这时我们可以把每...
php实现微信支付 微信支付文档地址: https://pay.weixin.qq.com/wiki/doc/api/i...
本文转载自微信公众号「程序员历小冰」,转载本文请联系程序员历小冰公众号。 疫...
六、XML展望 任何一项新技术的产生都是有其需求背景的,XML的诞生是在HTML遇到不...
背景 该问题来自某客户,据描述,他们在部署 MySQL 主从复制时,有时候仅在主库...
微软官方博客于 2 月初再次发布提示,将会在 3 月 9 日停止对经典版 Edge 浏览器...