bcachefs: Btree split improvement
authorKent Overstreet <kent.overstreet@linux.dev>
Wed, 16 Nov 2022 02:52:12 +0000 (21:52 -0500)
committerKent Overstreet <kent.overstreet@linux.dev>
Sun, 22 Oct 2023 21:09:46 +0000 (17:09 -0400)
commit4fcdd6ec345e1aeed23fbdbe53d62965c1a79b99
treecfe98f33f2222015fb944dfa01c944c6b5e89234
parent0f35e0860a73a35e8c3aa1afebc45e75eb2fbae6
bcachefs: Btree split improvement

This improves the bkey_format calculation when splitting btree nodes.
Previously, we'd use a format calculated for the original node for the
lower of the two new nodes.

This was particularly bad on sequential insertions, where we iteratively
split the last btree node, whos format has to include KEY_MAX.

Now, we calculate formats precisely for the keys the two new nodes will
contain. This also should make splitting a bit more efficient, since
we're only copying keys once (from the original node to the new node,
instead of new node, replacement node, then upper split).

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
fs/bcachefs/bkey_sort.c
fs/bcachefs/bset.h
fs/bcachefs/btree_update_interior.c