データベースとデータ構造におけるB木とB+木の違い

2024-04-02

B木とB+木の比較：データベースとデータ構造における違い

構造

B木

各ノードは、最大M個のキーとM+1個の子ポインタを持つ
データはすべてのノードに格納
葉ノードは同じ深さ
検索は、ルートノードから子ノードをたどってキーを比較しながら行う

データは葉ノードのみ格納
葉ノードは連結リストで繋がれている

性能

検索

B木とB+木は、どちらもO(logN)の計算量でデータ検索が可能
B+木は、葉ノードのみデータを持つため、データ量が大きくなるとB木よりも検索速度が速くなる

挿入

B+木は、葉ノードにのみデータが格納されるため、B木よりも挿入処理が高速

B木は、すべてのノードにデータが格納されるため、B+木よりもメモリ使用量が多くなる
B+木は、葉ノードが連結リストで繋がれているため、B木よりも実装が複雑

用途

データの検索と挿入・削除の頻度がほぼ同じ場合
メモリ使用量が重要な場合

データの検索頻度が高い場合
データ量が大きい場合

B木とB+木は、どちらも効率的なデータ構造ですが、それぞれ異なる特性を持っています。用途に合わせて適切なデータ構造を選択することが重要です。

B木とB+木のサンプルコード

class BNode:
    def __init__(self, m):
        self.m = m
        self.keys = []
        self.children = []

    def is_full(self):
        return len(self.keys) == self.m

    def insert(self, key, child):
        if self.is_full():
            self.split()

        i = self.find_insert_position(key)
        self.keys.insert(i, key)
        self.children.insert(i + 1, child)

    def split(self):
        mid = len(self.keys) // 2
        new_node = BNode(self.m)

        new_node.keys = self.keys[mid:]
        new_node.children = self.children[mid + 1:]

        self.keys = self.keys[:mid]
        self.children = self.children[:mid + 1]

    def find_insert_position(self, key):
        for i, k in enumerate(self.keys):
            if key < k:
                return i
        return len(self.keys)

class BTree:
    def __init__(self, m):
        self.m = m
        self.root = BNode(m)

    def insert(self, key):
        self.root.insert(key, None)


# Example usage
tree = BTree(3)
tree.insert(10)
tree.insert(20)
tree.insert(30)
tree.insert(40)
tree.insert(50)

print(tree.root.keys)

class BNode:
    def __init__(self, m):
        self.m = m
        self.keys = []
        self.pointers = []

    def is_full(self):
        return len(self.keys) == self.m

    def insert(self, key, pointer):
        if self.is_full():
            self.split()

        i = self.find_insert_position(key)
        self.keys.insert(i, key)
        self.pointers.insert(i + 1, pointer)

    def split(self):
        mid = len(self.keys) // 2
        new_node = BNode(self.m)

        new_node.keys = self.keys[mid:]
        new_node.pointers = self.pointers[mid + 1:]

        self.keys = self.keys[:mid]
        self.pointers = self.pointers[:mid + 1]

    def find_insert_position(self, key):
        for i, k in enumerate(self.keys):
            if key < k:
                return i
        return len(self.keys)

class BPlusTree:
    def __init__(self, m):
        self.m = m
        self.root = BNode(m)

    def insert(self, key):
        self.root.insert(key, None)


# Example usage
tree = BPlusTree(3)
tree.insert(10)
tree.insert(20)
tree.insert(30)
tree.insert(40)
tree.insert(50)

print(tree.root.keys)