发布时间：2025-06-24 19:45:21  作者：北方职教升学中心  阅读量：792

三、学习建议

刷面试题虽能在短期内提升应试能力，但可能存在准备的问题没考，没准备的问题却被问到的情况。

B + 树的所有叶子节点通过一个双向指针连接，使得范围查找的效率更高。B 树和 B + 树的基本概念

（一）从二叉树到 B 树

（二）B + 树与 B 树的区别

三、

以下是根据上述视频内容涉及的部分概念，编写的一些相关 Java 示例代码，用于辅助理解其中提到的数据结构相关内容：

二叉树节点定义示例

class BinaryTreeNode {    int value;    BinaryTreeNode left;    BinaryTreeNode right;    public BinaryTreeNode(int value) {        this.value = value;        this.left = null;        this.right = null;    }}

二叉查找树插入节点示例方法

class BinarySearchTree {    private BinaryTreeNode root;    public void insert(int value) {        root = insertRecursive(root, value);    }    private BinaryTreeNode insertRecursive(BinaryTreeNode current, int value) {        if (current == null) {            return new BinaryTreeNode(value);        }        if (value < current.value) {            current.left = insertRecursive(current.left, value);        } else if (value > current.value) {            current.right = insertRecursive(current.right, value);        }        return current;    }}

平衡二叉树（AVL 树）节点定义及左旋右旋示例方法（简化示意，实际更复杂）

class AVLTreeNode {    int value;    AVLTreeNode left;    AVLTreeNode right;    int height;    public AVLTreeNode(int value) {        this.value = value;        this.left = null;        this.right = null;        this.height = 1;    }}class AVLTree {    private AVLTreeNode root;    // 获取节点高度    private int height(AVLTreeNode node) {        if (node == null) {            return 0;        }        return node.height;    }    // 获取平衡因子    private int getBalanceFactor(AVLTreeNode node) {        if (node == null) {            return 0;        }        return height(node.left) - height(node.right);    }    // 右旋操作（简化示意）    private AVLTreeNode rightRotate(AVLTreeNode y) {        AVLTreeNode x = y.left;        AVLTreeNode T2 = x.right;        x.right = y;        y.left = T2;        y.height = Math.max(height(y.left), height(y.right)) + 1;        x.height = Math.max(height(x.left), height(x.right)) + 1;        return x;    }    // 左旋操作（简化示意）    private AVLTreeNode leftRotate(AVLTreeNode x) {        AVLTreeNode y = x.right;        AVLTreeNode T2 = y.left;        y.left = x;        x.right = T2;        x.height = Math.max(height(x.left), height(x.right)) + 1;        y.height = Math.max(height(y.left), height(y.right)) + 1;        return y;    }    // 插入节点并保持平衡（简化示意，实际需更多处理）    public void insert(int value) {        root = insertRecursive(root, value);    }    private AVLTreeNode insertRecursive(AVLTreeNode current, int value) {        if (current == null) {            return new AVLTreeNode(value);        }        if (value < current.value) {            current.left = insertRecursive(current.left, value);        } else if (value > current.value) {            current.right = insertRecursive(current.right, value);        } else {            // 不允许插入重复值，这里可根据实际需求处理            return current;        }        current.height = 1 + Math.max(height(current.left), height(current.right));        int balanceFactor = getBalanceFactor(current);        // 左左情况        if (balanceFactor > 1 && value < current.left.value) {            return rightRotate(current);        }        // 右右情况        if (balanceFactor < -1 && value > current.right.value) {            return leftRotate(current);        }        // 左右情况        if (balanceFactor > 1 && value > current.left.value) {            current.left = leftRotate(current.left);            return rightRotate(current);        }        // 右左情况        if (balanceFactor < -1 && value < current.right.value) {            current.right = rightRotate(current.right);            return leftRotate(current);        }        return current;    }}

B 树节点定义示例（简化示意，未包含完整 B 树操作逻辑）

import java.util.ArrayList;import java.util.List;class BTreeNode {    // 存储关键字    List<Integer> keys = new ArrayList<>();    // 存储子节点    List<BTreeNode> children = new ArrayList<>();    boolean isLeaf;    public BTreeNode(boolean isLeaf) {        this.isLeaf = isLeaf;    }    // 添加关键字    public void addKey(int key) {        keys.add(key);    }    // 添加子节点    public void addChild(BTreeNode child) {        children.add(child);    }}

B + 树节点定义示例（简化示意，未包含完整 B + 树操作逻辑）

import java.util.ArrayList;import java.util.List;class BPlusTreeNode {    // 存储关键字    List<Integer> keys = new ArrayList<>();    // 存储指向子节点的指针（非叶子节点）或数据（叶子节点）    List<Object> pointers = new ArrayList<>();    boolean isLeaf;    public BPlusTreeNode(boolean isLeaf) {        this.isLeaf = isLeaf;    }    // 添加关键字    public void addKey(int key) {        keys.add(key);    }    // 添加指针或数据    public void addPointer(Object pointer) {        pointers.add(pointer);    }}

请注意，上述代码只是对视频中提及的数据结构概念进行简单的 Java 代码实现示例，用于辅助理解相关结构特点及操作逻辑的大致思路。为何使用 B 树或 B + 树作为索引结构

原因是 AVL 树（平衡二叉树）的高度比 B + 树的高度要高，而树的高度意味着磁盘 I/O 的数量。以下是一个简单的 Python 代码示例，用于创建一个简单的树结构（这里只是示意，与 B 树和 B + 树不完全相同，但可以帮助理解节点和数据存储概念）：

# 定义树节点类class TreeNode:    def __init__(self, data=None):        self.data = data        self.children = []# 创建一个简单的树（类似B树的节点存储数据方式）root = TreeNode(10)node2 = TreeNode(5)node3 = TreeNode(15)root.children = [node2, node3]

1. 子树数量与关键字关系：B + 树的子树数量等于关键字数量，而 B 树的子树数量是关键字数量加 1。

   二、磁盘 I/O 的性能很低，特别是随机磁盘 I/O，因为磁盘 I/O 需要经过系统传逻辑地址、

六、B 树和 B + 树的应用场景

B 树和 B + 树一般应用在文件系统或者数据库系统中，主要目的是减少磁盘 I/O 带来的性能损耗。

四、以 MySQL 的 InnoDB 为例，当执行select语句查询一条数据时，InnoDB 需要从磁盘读取数据，这个过程涉及磁盘 I/O 和磁盘随机 I/O。希望大家通过对 B 树和 B + 树的学习，能更好地理解数据结构在实际应用中的重要性，提升自己的知识储备。B 树和 B + 树的特点总结

（一）B 树特点

1. 在 B 树中每个节点都包含索引及数据，所以树的层高相对较高。真正完整且高效的实现这些数据结构会涉及到更多复杂的细节处理，比如节点的分裂、这样在查找目标数据时，根据索引从 B + 树中查找，由于 B + 树的分支比较多，只需较少次数的磁盘 I/O 就能找到对应的数据。引言

   二、为何使用 B 树或 B + 树作为索引结构

   五、为了减少磁盘 I/O 的次数，文件系统或者数据库才会采用 B 树或者 B + 树。

   目录

   B 树和 B + 树：数据结构的深度解析

   一、今天，我们就来深入剖析 B 树和 B + 树，解答这些疑问，并分享一些相关的学习资源。引言

   在数据结构与算法领域，B 树和 B + 树是常常被提及的重要概念。

2. B 树：是一种多路平衡查找树，满足平衡二叉树的规则，但可以有多个子树。二叉查找树在二叉树的基础上增加了规则，即左子树所有节点值小于根节点，右子树所有节点值大于根节点。