Does WT supports btree node merge?

baoshang young

unread,

Jan 21, 2021, 4:51:54 AM1/21/21

to wiredtiger-users

The btree node will split when inserting data to the btree continuously. Does WT supports btree node merge when deleting data in the btree continuously. I have check the codebase, but I could not find any logical of btree node merge. Why WT use this design?

Keith Bostic

unread,

Jan 21, 2021, 11:21:02 AM1/21/21

to wiredtiger-users

On Thursday, January 21, 2021 at 1:51:54 AM UTC-8 zaor...@gmail.com wrote:

The btree node will split when inserting data to the btree continuously. Does WT supports btree node merge when deleting data in the btree continuously. I have check the codebase, but I could not find any logical of btree node merge. Why WT use this design?

Btree pages will not be discarded until they are entirely emptied, but once a page is emptied, it will be discarded.

baoshang young

unread,

Jan 22, 2021, 8:38:15 PM1/22/21

to wiredtiger-users

Thans a lot for your reply. And I have a another question about when we decrease the Btree’s level? Because I think the Btree’s level is lower, the search is faster.

Keith Bostic

unread,

Jan 22, 2021, 9:16:56 PM1/22/21

to wiredtiger-users

On Friday, January 22, 2021 at 5:38:15 PM UTC-8 zaor...@gmail.com wrote:

And I have a another question about when we decrease the Btree’s level?

When leaf pages are emptied, they are removed from internal pages; when internal pages are emptied, they are removed similarly, decreasing the (local) Btree level.

baoshang young

unread,

Jan 22, 2021, 11:03:00 PM1/22/21

to wiredtiger-users

Thanks a lot. Does local Btree means the subtree? That is to say the overall btree’s level is not changed, am I right? Maybe I should read the code. Could you please tell me where I could find the logical of decreasing the Bree level?

Keith Bostic

unread,

Jan 23, 2021, 11:44:22 AM1/23/21

to wiredtiger-users

On Friday, January 22, 2021 at 8:03:00 PM UTC-8 zaor...@gmail.com wrote:

Does local Btree means the subtree? That is to say the overall btree’s level is not changed, am I right?

Yes; over time I would expect the overall btree level to decrease, but it's done incrementally.

Maybe I should read the code. Could you please tell me where I could find the logical of decreasing the Bree level?

The code you're looking for is in src/evict_page.c, for example, __evict_delete_ref(), calling into __wt_split_reverse().

baoshang young

unread,

Jan 23, 2021, 10:37:35 PM1/23/21

to wiredtiger-users

Thanks for your help.

Best regards

Zaorang

Reply all

Reply to author

Forward