Find which child a key should go to
(self, key: Any)
| 899 | self.children.extend(right_sibling.children) |
| 900 | |
| 901 | def find_child_index(self, key: Any) -> int: |
| 902 | """Find which child a key should go to""" |
| 903 | # Validate node structure |
| 904 | if len(self.children) == 0: |
| 905 | raise ValueError("BranchNode has no children") |
| 906 | if len(self.keys) != len(self.children) - 1: |
| 907 | raise ValueError( |
| 908 | f"Invalid branch structure: {len(self.keys)} keys, {len(self.children)} children" |
| 909 | ) |
| 910 | |
| 911 | # Use optimized bisect module for binary search |
| 912 | # bisect_right returns the insertion point for key in keys |
| 913 | # For B+ trees: if key <= separator, go left; if key > separator, go right |
| 914 | index = bisect.bisect_right(self.keys, key) |
| 915 | |
| 916 | # Validate result |
| 917 | if index >= len(self.children): |
| 918 | raise ValueError( |
| 919 | f"Child index {index} out of range (have {len(self.children)} children)" |
| 920 | ) |
| 921 | |
| 922 | return index |
| 923 | |
| 924 | def get_child(self, key: Any) -> Node: |
| 925 | """Get the child node where a key would be found""" |
no outgoing calls