B+ Tree with single array node optimization.
| 226 | |
| 227 | |
| 228 | class OptimizedBPlusTree: |
| 229 | """B+ Tree with single array node optimization.""" |
| 230 | |
| 231 | def __init__(self, capacity: int = 128): |
| 232 | self.capacity = capacity |
| 233 | self.root = OptimizedLeafNode(capacity) |
| 234 | self.leaves = self.root |
| 235 | |
| 236 | def __getitem__(self, key) -> Any: |
| 237 | """Lookup with optimized nodes.""" |
| 238 | node = self.root |
| 239 | while not node.is_leaf(): |
| 240 | node = node.get_child(key) |
| 241 | |
| 242 | value = node.get(key) |
| 243 | if value is None: |
| 244 | raise KeyError(key) |
| 245 | return value |
| 246 | |
| 247 | def __setitem__(self, key, value): |
| 248 | """Insert with optimized nodes.""" |
| 249 | result = self._insert_recursive(self.root, key, value) |
| 250 | if result is not None: |
| 251 | # Root split, create new root |
| 252 | split_key, right_node = result |
| 253 | new_root = OptimizedBranchNode(self.capacity) |
| 254 | new_root.data[new_root.capacity] = self.root # First child |
| 255 | new_root.insert(split_key, right_node) |
| 256 | self.root = new_root |
| 257 | |
| 258 | def _insert_recursive(self, node, key, value) -> Optional[Tuple]: |
| 259 | """Recursive insert.""" |
| 260 | if node.is_leaf(): |
| 261 | return node.insert(key, value) |
| 262 | else: |
| 263 | child = node.get_child(key) |
| 264 | result = self._insert_recursive(child, key, value) |
| 265 | if result is not None: |
| 266 | return node.insert(result[0], result[1]) |
| 267 | return None |
| 268 | |
| 269 | def items(self, start_key=None, end_key=None) -> Iterator[Tuple[Any, Any]]: |
| 270 | """Iterate over key-value pairs in range.""" |
| 271 | # Find start leaf |
| 272 | if start_key is None: |
| 273 | current = self.leaves |
| 274 | else: |
| 275 | current = self.root |
| 276 | while not current.is_leaf(): |
| 277 | current = current.get_child(start_key) |
| 278 | |
| 279 | # Iterate through leaves |
| 280 | while current is not None: |
| 281 | start_pos = 0 |
| 282 | if start_key is not None and current is self.root: |
| 283 | start_pos = current.find_position(start_key) |
| 284 | |
| 285 | for i in range(start_pos, current.num_keys): |
no outgoing calls