Good question! Appending at the end (or near the end) is actually the best-case scenario in my B-tree implementation, because it leaves the right-most leaf fully packed, unlike a classic B-tree which keeps it at half-capacity. More info here: https://github.com/hoytech/negentropy/blob/master/cpp/negentropy/storage/btree/core.h#L15-L31
Making multiple updates to the B-tree in the same transaction is also highly optimised: The modified nodes are edited in-place in memory, and only committed to the DB at the end of the transaction. So on average, inserting 40 or fewer records at the right edge of the tree in one transaction will require only 1 DB read and 1 DB write (in addition to the metadata page).
Doug Hoyte /
npub1yx…8qud4
2024-09-13 19:24:01
in reply to nevent1q…cqqg
Author Public Key
npub1yxprsscnjw2e6myxz73mmzvnqw5kvzd5ffjya9ecjypc5l0gvgksh8qud4Published at
2024-09-13 19:24:01Event JSON
{
"id": "00c29d441a31921bf775d95b8d3b80e6f77cc86350c43b1707f228b027a3d2cc",
"pubkey": "218238431393959d6c8617a3bd899303a96609b44a644e973891038a7de8622d",
"created_at": 1726255441,
"kind": 1,
"tags": [
[
"client",
"oddbean"
],
[
"e",
"8623be03632bdf85e140c275fdf7f39b20e1393c381164f5b25662724663058a",
"",
"root"
],
[
"e",
"89f721d45793f940cb7453be76a564ff2a1d3ba3cd31ba0b501c2c38cbc83d0f",
"",
"reply"
],
[
"p",
"218238431393959d6c8617a3bd899303a96609b44a644e973891038a7de8622d"
],
[
"p",
"6140478c9ae12f1d0b540e7c57806649327a91b040b07f7ba3dedc357cab0da5"
]
],
"content": "Good question! Appending at the end (or near the end) is actually the best-case scenario in my B-tree implementation, because it leaves the right-most leaf fully packed, unlike a classic B-tree which keeps it at half-capacity. More info here: https://github.com/hoytech/negentropy/blob/master/cpp/negentropy/storage/btree/core.h#L15-L31\n\nMaking multiple updates to the B-tree in the same transaction is also highly optimised: The modified nodes are edited in-place in memory, and only committed to the DB at the end of the transaction. So on average, inserting 40 or fewer records at the right edge of the tree in one transaction will require only 1 DB read and 1 DB write (in addition to the metadata page).",
"sig": "b8eb8614223866ff2884032302ef324138d8723963ed6ce70fb31182fdb4138f7c9ce09feb44b9672219ab31ff435751d71aa0c386f2fd21a8d47c5d2460a17c"
}