Какие знаешь операции в B-Tree?

Какие знаешь операции в B-Tree?

B-Tree — это самобалансирующееся дерево поиска, которое используется в базах данных и файловых системах для эффективного хранения больших объемов данных на диске. Это одна из ключевых структур данных в production системах.

1. Основные свойства B-Tree

B-Tree порядка m имеет следующие свойства:

"""
B-Tree порядка 3 (t=2):
- Каждый узел содержит не более 2*t-1 = 3 ключей
- Каждый узел содержит не более 2*t = 4 дочерних узлов
- Все листья находятся на одном уровне (сбалансировано)
- Внутренние узлы содержат от t-1 = 1 до 2*t-1 = 3 ключей

Пример структуры:
       [10, 50]
      /    |    \\
    [5]  [30]  [60, 80]
"""

2. Операция SEARCH (поиск)

Поиск элемента в B-Tree работает как бинарный поиск, но на каждом уровне многих ключей:

class BTreeNode:
    def __init__(self, is_leaf=False):
        self.keys = []
        self.children = []
        self.is_leaf = is_leaf
    
    def search(self, key):
        """Поиск ключа в поддереве с корнем в этом узле"""
        i = 0
        
        # Найти первый ключ больший или равный key
        while i < len(self.keys) and key > self.keys[i]:
            i += 1
        
        # Если найденный ключ совпадает, ключ в этом узле
        if i < len(self.keys) and key == self.keys[i]:
            return True
        
        # Если это листовой узел, ключа нет
        if self.is_leaf:
            return False
        
        # Рекурсивный поиск в дочернем узле
        return self.children[i].search(key)

# Пример использования
class BTree:
    def __init__(self, t):
        self.root = BTreeNode(is_leaf=True)
        self.t = t  # Минимальная степень
    
    def search(self, key):
        """Поиск ключа в дереве, O(log n)"""
        return self.root.search(key)

# Использование
btree = BTree(t=2)
print(btree.search(30))  # False (дерево еще пусто)

Сложность поиска: O(log n) — очень эффективно даже для миллиардов элементов.

3. Операция INSERT (вставка)

Вставка — это самая сложная операция, так как нужно поддерживать баланс дерева:

class BTreeNode:
    def __init__(self, is_leaf=False, t=2):
        self.keys = []
        self.children = []
        self.is_leaf = is_leaf
        self.t = t
    
    def insert_non_full(self, key):
        """Вставить ключ в узел, который не заполнен"""
        i = len(self.keys) - 1
        
        if self.is_leaf:
            # Добавить ключ в отсортированный порядок
            self.keys.append(None)
            while i >= 0 and key < self.keys[i]:
                self.keys[i + 1] = self.keys[i]
                i -= 1
            self.keys[i + 1] = key
        else:
            # Найти дочерний узел, куда должен идти ключ
            while i >= 0 and key < self.keys[i]:
                i -= 1
            i += 1
            
            # Если дочерний узел полный, разделить его
            if len(self.children[i].keys) == (2 * self.t - 1):
                self.split_child(i)
                if key > self.keys[i]:
                    i += 1
            
            self.children[i].insert_non_full(key)
    
    def split_child(self, i):
        """Разделить дочерний узел в позиции i"""
        t = self.t
        y = self.children[i]
        z = BTreeNode(is_leaf=y.is_leaf, t=t)
        
        # Скопировать последние t-1 ключей из y в z
        z.keys = y.keys[t-1:]
        y.keys = y.keys[:t-1]
        
        # Если не листовой, скопировать дочерние указатели
        if not y.is_leaf:
            z.children = y.children[t:]
            y.children = y.children[:t]
        
        # Вставить средний ключ в родителя
        self.keys.insert(i, y.keys[t-1])
        self.children.insert(i+1, z)

# Пример: вставка элементов
btree = BTree(t=2)
for key in [10, 20, 5, 6, 12, 30, 7, 17]:
    btree.insert(key)

# Дерево автоматически балансируется

Сложность вставки: O(log n) — дерево остается сбалансированным после каждой вставки.

4. Операция DELETE (удаление)

Удаление — самая сложная операция, требует множество случаев:

class BTreeNode:
    def delete(self, key):
        """Удалить ключ из поддерева с корнем в этом узле"""
        idx = 0
        while idx < len(self.keys) and self.keys[idx] < key:
            idx += 1
        
        if idx < len(self.keys) and self.keys[idx] == key:
            if self.is_leaf:
                # Случай 1: ключ в листовом узле
                self.keys.pop(idx)
            else:
                # Случай 2: ключ во внутреннем узле
                self.delete_internal_node(key, idx)
        elif not self.is_leaf:
            # Случай 3: ключ может быть в поддереве
            is_in_subtree = (idx == len(self.keys))
            
            # Если дочерний узел имеет минимум ключей, объединить или взять у соседа
            if len(self.children[idx].keys) < self.t:
                self.fill(idx)
            
            if is_in_subtree and idx > len(self.keys):
                self.children[idx-1].delete(key)
            else:
                self.children[idx].delete(key)
    
    def delete_internal_node(self, key, idx):
        """Удалить ключ из внутреннего узла"""
        key_to_delete = self.keys[idx]
        
        if len(self.children[idx].keys) >= self.t:
            # Предыдущий дочерний узел имеет достаточно ключей
            predecessor = self.get_predecessor(idx)
            self.keys[idx] = predecessor
            self.children[idx].delete(predecessor)
        elif len(self.children[idx+1].keys) >= self.t:
            # Следующий дочерний узел имеет достаточно ключей
            successor = self.get_successor(idx)
            self.keys[idx] = successor
            self.children[idx+1].delete(successor)
        else:
            # Оба дочерних узла имеют минимум ключей, объединить их
            self.merge(idx)
            self.children[idx].delete(key_to_delete)

# Сложность удаления: O(log n)

5. Операция SPLIT (разделение узла)

Разделение происходит, когда узел становится слишком заполненным:

"""
Разделение узла (t=2, максимум 3 ключа):

До разделения:
     [15] (родитель)
      |
  [5, 10, 15, 20]  <- переполнен (4 ключа)

После разделения:
      [10, 15] (родитель добавил средний ключ)
       /   |   \\
    [5]  [15]  [20]
"""

6. Практический пример: создание полного B-Tree

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(is_leaf=True, t=t)
        self.t = t
    
    def insert(self, key):
        """Вставить ключ в B-Tree"""
        root = self.root
        
        if len(root.keys) == 2 * self.t - 1:
            # Если корень полный, создать новый корень
            new_root = BTreeNode(is_leaf=False, t=self.t)
            new_root.children.append(self.root)
            new_root.split_child(0)
            self.root = new_root
        
        self.root.insert_non_full(key)
    
    def traverse(self, node=None, result=None):
        """Обойти дерево и вернуть все ключи в отсортированном порядке"""
        if node is None:
            node = self.root
        if result is None:
            result = []
        
        i = 0
        for i in range(len(node.keys)):
            if not node.is_leaf:
                result.extend(self.traverse(node.children[i], result))
            result.append(node.keys[i])
        
        if not node.is_leaf:
            result.extend(self.traverse(node.children[i+1], result))
        
        return result

# Использование
btree = BTree(t=2)
keys = [10, 20, 5, 6, 12, 30, 7, 17, 3, 11, 40]

for key in keys:
    btree.insert(key)

print("B-Tree (inorder):", btree.traverse())
# Output: [3, 5, 6, 7, 10, 11, 12, 17, 20, 30, 40]

7. Таблица операций B-Tree

8. Практическое применение

1. Базы данных (индексы):

PostgreSQL, MySQL используют B+ Tree для индексов

2. Файловые системы (NTFS, ext4):

Быстрый поиск файлов по имени

3. Key-Value хранилища (RocksDB, LevelDB):

Эффективное хранение и поиск данных на диске

9. B+ Tree (вариант для БД)

B+ Tree — это модификация B-Tree, где все данные хранятся в листьях:

"""
B+ Tree преимущества для БД:
- Листья связаны в список (быстрый range scan)
- Внутренние узлы только для навигации
- Лучше для дисковых операций (последовательное чтение листьев)
- Используется в практически всех реляционных БД
"""