B-trees are the workhorse on-disk index in almost every relational database -- Postgres's nbtree, SQLite's btree.c, MySQL's InnoDB. Their defining property: every node stays between t-1 and 2t-1 keys (where t is the tree's minimum degree), which is what keeps the tree shallow and every leaf at the same depth no matter how many keys you insert.

search and the node structure are done for you. Implement insert(key), _split_child(parent, index), and _insert_non_full(node, key):

• _split_child(parent, index): the child at parent.children[index] is full (2t-1 keys). Split it into two nodes of t-1 keys each, promoting the median key up into parent.
• _insert_non_full(node, key): insert key into node, which is guaranteed not to be full when this is called. For an internal node, this may require splitting one of its children first, before descending into it.
• insert(key): the entry point. Special case -- if the root is full, it must split first (the only way the tree grows taller), then insert as usual.

Constraints

After every insert, the tree must maintain real B-tree invariants:

• Every node's keys are sorted.
• Every non-root node has between t-1 and 2t-1 keys.
• An internal node with k keys has exactly k+1 children.
• Every leaf is at the same depth.

Real-world grounding

• Postgres's B-tree insertion (with page splits): nbtinsert.c
• SQLite's B-tree implementation: btree.c

Real implementations split disk pages instead of in-memory node objects, and add a lot more (concurrent access, page-level locking, right-sibling pointers for range scans) -- but the core "split full nodes on the way down, promote the median key" algorithm is exactly what you're implementing here.