Java面试常见问题:B-树和B+树
lipiwang 2024-11-21 17:42 4 浏览 0 评论
除了Java语法和并发编程方面这些必考内容，Java面试还经常会问到关于数据结构方面的问题。本文就来介绍两个在数据库和文件系统中常用的数据结构：B-树和B+树。需要注意的是：“B-树”中的短横不是减号，B表示平衡（Balance）的意思。
B-树
B-树是为了磁盘或其它存储设备而设计的一种平衡多叉搜索树。B-树与平衡二叉搜索树最大的不同在于，B-树的结点可以有许多孩子。B-树可以在O（logn）的时间复杂度内，实现插入、删除等动态操作，相比平衡二叉树，大大减少了IO的次数。
M阶B-树（M>2），代表一个树结点最多有M个子结点（查找路径），上图为3阶B-树。
B-树需要满足以下规则：
- 排序方式：每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它；
- 子结点数：根结点的子结点数为[2, M]，其他非叶结点的子结点数为[M/2, M]，向上取整；
- 关键字数：非叶结点的关键字数量为子结点数-1，如上图每个非叶结点有2个关键字，分成3个区间，分别指向3个子树；
- 叶子结点：所有叶子结点均在同一层，或者说根节点到每个叶子节点的长度都相同；
另外B-树的每个结点，除了有关键字key以外，还有value，也就是关键字记录的指针（地址）。
苹果电脑的HFS+文件系统，就采用了B树作为文件系统的索引。
B+树
B+树是B-树的一种变形，其与B-树的区别主要在于：
- 非叶子结点的子树指针与关键字个数相同；
- 非叶子结点的子树指针 P[i]，指向关键字值属于 [K[i], K[i+1]) 的子树，而B-树的子树结点关键字不包括 K[i]；
- 所有叶子结点增加了一个链指针；
- 所有关键字都在叶子结点出现。
上图是一个 M=3 的 B+树，非叶子结点的关键字个数和子树指针都是3个。第一个非叶子结点（5，10，20）的第一个指针 P1 指向的子树，只有一个叶子结点，P1对应的关键字5又出现在了叶子结点的关键字中。
B+树的应用
B+树适合应用于操作系统的文件索引和数据库索引。B+树相比于B树，在文件系统和数据库系统当中更有优势，原因如下：
- IO读写代价低
B+树的非叶结点不保存关键字记录的指针，只进行数据索引，B+树每个非叶节点所能保存的关键字大大增加。一次性读入内存中的关键字越多，也就意味着I/O读写次数越少。 - 查询效率稳定
B+树只有叶子结点保存了关键字记录的指针，任何关键字记录的查找都必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，数据查询效率相比B-树更加稳定。 - 有利于数据库扫描
B+树只需要遍历叶子结点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的区间查询，B+树有着更高的性能。
Mysql的InnoDB和MylSAM存储引擎都是用B+树实现索引结构。
我会持续更新关于物联网、云原生以及数字科技方面的文章，用简单的语言描述复杂的技术，也会偶尔发表一下对IT产业的看法，欢迎大家关注、转发和评论。
相关推荐
- Java 实体映射工具 MapStruct（jpa实体类映射类）
-
简介：让你的DO（业务实体对象），DTO（数据传输对象）数据转换更简单强大前言在软件架构中，分层式结构是最常见，各层之间有其独立且隔离的业务逻辑，也因而各层有自己的输入输出对象，也就是代码中见到各...
- @Date不管用怎么办，想少写get和setter方法，怎么办
-
学习交流群：293911833，有遇到问题的，可以加一下群，大家互相交流，一起进步今天在使用lombok的时候，为什么@Date不管用，是我映射没做好吗？还是其他的，后来查了一些大佬的资料终于找到问...
- Spring系列之集成MongoDB的2种方法
-
MongoDB是最流行的NoSQL数据库，SpringBoot是使用Spring的最佳实践。今天带大家讲一讲SpringBoot集成MongoDB的两种方式，MongoDB的安装自行去官网查询，本地开...
- Spring Boot集成SLF4j详解（springboot集成knife4j）
-
SpringBoot集成SLF4j详解：从基础到高级实践SLF4j（SimpleLoggingFacadeforJava）是一个日志门面框架，提供统一的日志接口，允许开发者灵活切换底层...
- 自定义代码生成器(上)（代码自动生成器）
-
1概述1.1介绍在项目开发过程中，有很多业务模块的代码是具有一定规律性的，例如controller控制器、service接口、service实现类、mapper接口、model实体类等等，这部分代...
- Java系统开发从入门到精通第四讲(文字版)
-
课程目标：了解重要的JavaAPI和一些必备框架的使用，这些都是系统开发的标配需要掌握日期时间APIJava8通过发布新的Date-TimeAPI(JSR310)来进一步加强对日期与时间...
- 重拾JAVA:这种编程语言为什么不行了?
-
全文共2322字，预计学习时长6分钟为了应对新工作，笔者在过去两周一直在重新熟悉一位老朋友：JAVA。我以JAVA开启了我的软件事业，与之共行了两年半左右的时间。但是随着容器和微服务的出现，JAVA很...
- 一款提高Java开发效率的工具（java怎么提高技术）
-
今天来介绍一款Java常用插件：Lombokhttps://projectlombok.org/通常在用Java代码开发项目过程中，都会建立各种各种的Bean类，如下：publicclassSea...
- JDK从8升级到21的问题集（jdk1.6升级到1.8要考虑的因素）
-
一、背景与挑战1.升级动因oOracle长期支持策略o现代特性需求：协程、模式匹配、ZGC等o安全性与性能的需求oAI新技术引入的版本要求2.项目情况o100+项目并行升级的协同作战o多技术栈并存o持...
- Lombok:让Java代码变得优雅简洁的秘密武器
-
Lombok：让Java代码变得优雅简洁的秘密武器在Java的世界里，代码量往往是一个开发者幸福感的重要衡量指标。代码写得越少，出错的可能性就越小，同时维护起来也更轻松。而Lombok正是这样一个让J...
- SpringToolSuite(STS)安装lombok插件
-
一、打开maven仓库，找到lombok所在的文件夹二、在命令行中运行java-jarlombok-1.18.20.jar，打开lombok插件安装的可视化界面。三、选择STS安装目录，点击Ins...
- 年末将至，Java 开发者必须了解的 15 个Java 顶级开源项目
-
专注于Java领域优质技术，欢迎关注作者：SnailClimbStar的数量统计于2019-12-29。1.JavaGuideGuide哥大三开始维护的，目前算是纯Java类型项目中Sta...
- 相见恨晚，一个架构师也不会用的Lombok注解
-
原创：不羡鸳鸯不羡仙，一行代码调半天。小姐姐味道（微信公众号ID：xjjdog），欢迎分享，转载请保留出处。我见过很多反对Lombok的同学，背地里又偷偷的把插件添加了进去，这是真香原理在搞鬼。嘴上说...
- 第二弹!安排!安利几个让你爽到爆的IDEA必备插件
-
作者：Guide哥来自：JavaGuide大家好，我是Guide哥。上一篇关于IDEA插件推荐的文章：《第一弹！安排！安利10个让你爽到爆的IDEA必备插件！》收到了很多小伙伴的好评，时隔大半个月...
- Java @Data注解（java @order注解）
-
1、@Data注解是lombok.jar包下的注解，该注解通常用在实体bean上，不需要写出set和get方法，但是具备实体bean所具备的方法，简化编程提高变成速度。2、@Data相当于@Gette...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- maven镜像 (69)
- undefined reference to (60)
- zip格式 (63)
- oracle over (62)
- date_format函数用法 (67)
- 在线代理服务器 (60)
- shell 字符串比较 (74)
- x509证书 (61)
- localhost (65)
- java.awt.headless (66)
- syn_sent (64)
- settings.xml (59)
- 弹出窗口 (56)
- applicationcontextaware (72)
- my.cnf (73)
- httpsession (62)
- pkcs7 (62)
- session cookie (63)
- java 生成uuid (58)
- could not initialize class (58)
- beanpropertyrowmapper (58)
- word空格下划线不显示 (73)
- jar文件 (60)
- jsp内置对象 (58)
- makefile编写规则 (58)