protected void doInsert(DBTreeRecord<?, ? extends NS> entry, LevelInfo levelInfo) {
		// I1
		NR node = doChooseSubtree(levelInfo.dstLevel, entry.getBounds());

		// I2
		if (node.getType() == NodeType.LEAF) {
			@SuppressWarnings("unchecked")
			DR d = (DR) entry;
			doSetParentKey(d, node.getKey(), cachedDataChildren);
		}
		else {
			@SuppressWarnings("unchecked")
			NR n = (NR) entry;
			doSetParentKey(n, node.getKey(), cachedNodeChildren);
		}
		for (NR parent = node; parent != null; parent = getParentOf(parent)) {
			int newDataCount = parent.getDataCount() + entry.getDataCount();
			parent.setDataCount(newDataCount);
		}
		int newChildCount = node.getChildCount() + 1;
		node.setChildCount(newChildCount);

		// I4 - I'm having integrity issues unless this comes before overflow treatments		
		if (newChildCount == 1) {
			assert node == root;
			node.setShape(entry.getBounds());
		}
		else {
			for (NR parent = node; parent != null; parent = getParentOf(parent)) {
				parent.setShape(parent.getShape().unionBounds(entry.getBounds()));
			}
		}

		// I3
		NR split = null;
		if (newChildCount > maxChildren) {
			split = doOverflowTreatment(node, levelInfo);
		}
		// NOTE: Depth should never increase more than once per insert
		int savedLevel = levelInfo.dstLevel;
		for (NR propa = node, parent = getParentOf(propa); split != null; //
				propa = parent, //
				parent = getParentOf(propa), //
				split = doOverflowTreatment(propa, levelInfo.decLevel())) {
			if (parent == null) {
				assert propa == root;
				assert levelInfo.dstLevel == 0;
				root = nodeStore.create();
				root.setParentKey(-1);
				cachedNodeChildren.put(root.getKey(), new ArrayList<>(maxChildren));
				root.setShape(propa.getShape().unionBounds(split.getShape()));
				root.setType(propa.getType().getParentType());
				root.setChildCount(2);
				root.setDataCount(propa.getDataCount() + split.getDataCount());
				doSetParentKey(propa, root.getKey(), cachedNodeChildren);
				doSetParentKey(split, root.getKey(), cachedNodeChildren);
				leafLevel++;
				levelInfo.dstLevel = savedLevel;
				levelInfo.incDepth();
				return;
			}
			newChildCount = parent.getChildCount() + 1;
			parent.setChildCount(newChildCount);
			if (newChildCount <= maxChildren) {
				break;
			}
		}
		levelInfo.dstLevel = savedLevel;
	}
The Split algorithm as defined in Section 4.2 of the paper.

@param n the node to split
@return the new node (containing the second group)
Ghidra/Debug/ProposedUtils/src/main/java/ghidra/util/database/spatial/AbstractRStarConstraintsTree.java