Leaf node with single array optimization.
| 17 | |
| 18 | |
| 19 | class OptimizedLeafNode: |
| 20 | """Leaf node with single array optimization.""" |
| 21 | |
| 22 | def __init__(self, capacity: int): |
| 23 | self.capacity = capacity |
| 24 | self.num_keys = 0 |
| 25 | # Pre-allocate single array for better memory locality |
| 26 | self.data = [None] * (capacity * 2) |
| 27 | self.next: Optional["OptimizedLeafNode"] = None |
| 28 | |
| 29 | def is_leaf(self) -> bool: |
| 30 | return True |
| 31 | |
| 32 | def find_position(self, key) -> int: |
| 33 | """Binary search using only the keys portion of data array.""" |
| 34 | return bisect.bisect_left(self.data, key, 0, self.num_keys) |
| 35 | |
| 36 | def get_child(self, key) -> "OptimizedLeafNode": |
| 37 | """Leaf nodes don't have children.""" |
| 38 | return self |
| 39 | |
| 40 | def insert(self, key, value) -> Optional[Tuple[Any, "OptimizedLeafNode"]]: |
| 41 | """Insert with optimized array access.""" |
| 42 | pos = self.find_position(key) |
| 43 | |
| 44 | # Update existing key |
| 45 | if pos < self.num_keys and self.data[pos] == key: |
| 46 | self.data[self.capacity + pos] = value |
| 47 | return None |
| 48 | |
| 49 | # Check if split needed |
| 50 | if self.num_keys >= self.capacity: |
| 51 | return self._split_and_insert(pos, key, value) |
| 52 | |
| 53 | # Shift in single operation |
| 54 | if pos < self.num_keys: |
| 55 | # Move keys |
| 56 | self.data[pos + 1 : self.num_keys + 1] = self.data[pos : self.num_keys] |
| 57 | # Move values |
| 58 | start_val = self.capacity + pos |
| 59 | end_val = self.capacity + self.num_keys |
| 60 | self.data[start_val + 1 : end_val + 1] = self.data[start_val:end_val] |
| 61 | |
| 62 | # Insert |
| 63 | self.data[pos] = key |
| 64 | self.data[self.capacity + pos] = value |
| 65 | self.num_keys += 1 |
| 66 | return None |
| 67 | |
| 68 | def _split_and_insert( |
| 69 | self, pos: int, key, value |
| 70 | ) -> Tuple[Any, "OptimizedLeafNode"]: |
| 71 | """Split node and insert.""" |
| 72 | new_node = OptimizedLeafNode(self.capacity) |
| 73 | mid = self.capacity // 2 |
| 74 | |
| 75 | # Create temporary sorted list with new element |
| 76 | all_keys = [] |
no outgoing calls