往期链接

10 B+树(B+ Tree)

S1 说明

1. 数据结构
B+树是一种自平衡的树数据结构,主要用于数据库和文件系统中,具有以下特征:

  • 节点结构:
    • 内部节点:仅存储键,用于指引搜索。
    • 叶子节点:存储实际的数据记录,并通过指针顺序链接,形成链表。
  • 高度平衡:所有叶子节点在同一层,确保访问时间一致。
  • 度:每个节点可以有多个子节点,具体数量取决于树的度数(最小度数 t)。

2. 特点

  • 高效的查找:由于数据仅存储在叶子节点,查找操作通常更快。
  • 范围查询:叶子节点的链表结构使得范围查询非常高效。
  • 动态调整:插入和删除操作可以动态调整树的形状,保持平衡。
  • 空间利用率高:内部节点仅存储键,可以提高存储效率。

3. 应用领域

  • 数据库系统:用于索引数据库中的数据,以提高查询效率。
  • 文件系统:用于管理文件和目录的存储,支持快速访问和检索。
  • 内存数据库:在内存中高效存储数据,以提供快速访问。

S2 B+树和B树的区别

B+树和B树是两种广泛使用的自平衡搜索树,虽然它们在结构和功能上有许多相似之处,但也有一些关键的区别:

1. 节点结构

  • B树:每个节点可以存储多个键值对和指向子节点的指针。每个节点中的键可以用于查找、插入和删除。
  • B+树:内部节点仅存储键,而不存储实际的数据。所有数据都存储在叶子节点中。内部节点的主要作用是引导搜索。

2. 叶子节点

  • B树:叶子节点不一定形成一个链表,数据散布在各个节点中。
  • B+树:所有叶子节点通过指针相连,形成一个链表。这使得范围查询更高效,因为可以顺序访问所有叶子节点。

3. 搜索效率

  • B树:搜索时可能需要在多个节点中查找数据。
  • B+树:由于所有数据在叶子节点中,搜索时可以直接找到叶子节点,避免了在内部节点中查找数据的复杂性。

4. 插入和删除

  • B树:每次插入或删除可能会影响多个节点的结构。
  • B+树:插入和删除操作主要影响叶子节点,内部节点的结构相对稳定。

5. 空间利用率

  • B树:由于每个节点存储键值对,可能会存在空间浪费。
  • B+树:内部节点只存储键,通常能更高效地利用空间。

6. 应用场景

  • B树:适用于对数据的随机访问和修改频繁的场景。
  • B+树:常用于数据库和文件系统,尤其在需要进行范围查询和顺序访问时表现更好。

S3 示例

from graphviz import Digraph

class BPlusTreeNode:
    def __init__(self, order, is_leaf=False):
        self.order = order  # B+ 树的阶数
        self.is_leaf = is_leaf  # 是否为叶子节点
        self.keys = []  # 键值列表
        self.children = []  # 子节点指针或数据指针
        self.next = None  # 叶子节点的下一个叶子节点

class BPlusTree:
    def __init__(self, order=5):
        self.root = BPlusTreeNode(order, True)
        self.order = order

    def insert(self, key):
        """
        向 B+ 树中插入一个键值
        """
        node = self.root
        parents = []
        # 找到叶子节点
        while not node.is_leaf:
            parents.append(node)
            index = self._find_index(node.keys, key)
            node = node.children[index]

        # 插入键值到叶子节点
        self._insert_into_leaf(node, key)

        # 检查是否需要分裂
        while len(node.keys) > self.order - 1:
            if node == self.root:
                # 根节点分裂
                new_node, mid_key = self._split_node(node)
                new_root = BPlusTreeNode(self.order)
                new_root.keys = [mid_key]
                new_root.children = [node, new_node]
                self.root = new_root
                break
            else:
                parent = parents.pop()
                new_node, mid_key = self._split_node(node)
                index = self._find_index(parent.keys, mid_key)
                parent.keys.insert(index, mid_key)
                parent.children.insert(index + 1, new_node)
                node = parent

    def _split_node(self, node):
        """
        分裂节点,返回新节点和提升的键值
        """
        mid_index = (self.order - 1) // 2
        mid_key = node.keys[mid_index]

        # 创建新节点
        new_node = BPlusTreeNode(self.order, node.is_leaf)
        new_node.keys = node.keys[mid_index + (0 if node.is_leaf else 1):]
        new_node.children = node.children[mid_index + 1:]

        # 更新当前节点
        node.keys = node.keys[:mid_index + (1 if node.is_leaf else 0)]
        node.children = node.children[:mid_index + 1]

        if node.is_leaf:
            # 更新叶子节点的 next 指针
            new_node.next = node.next
            node.next = new_node
        return new_node, mid_key

    def _insert_into_leaf(self, leaf, key):
        """
        将键值插入到叶子节点中
        """
        index = self._find_index(leaf.keys, key)
        leaf.keys.insert(index, key)
        leaf.children.insert(index, key)  # 叶子节点的 children 存储数据,这里简化为与键值相同

    def _find_index(self, keys, key):
        """
        找到应插入的位置
        """
        for i, item in enumerate(keys):
            if key < item:
                return i
        return len(keys)

    def search(self, key):
        """
        在 B+ 树中搜索键值
        """
        node = self.root
        while not node.is_leaf:
            index = self._find_index(node.keys, key)
            node = node.children[index]
        for i, item in enumerate(node.keys):
            if item == key:
                return node.children[i]
        return None

    def display(self, node=None, level=0):
        """
        显示 B+ 树结构
        """
        node = node or self.root
        if node.is_leaf:
            print
10-19 01:42