About TODO Blog RSS Old blog Projects Gallery Notes

Fri, 07 Dec 2007

B(something)-tree vs RB-tree. On-disk allocations.

In the previous article it was shown, how btree and rbtree behave with allocations are being done in memory. In such conditions btree should suck compared to rbtree, and generally it is true, although in some conditions its insert speed can be even slightly higher htan rbtree.

Now, let's check how they behave when all allocations are performed from disk.
Below graph shows insert speed for both rbtree and btree in such conditions, each node was allocated with 1024+sizeof(node) offset from previous one so that readahead and thus cached disk apges would not influence the results.
Totally 1 million keys were inserted into the tree.
Search speed is roughly the same as with in-memory tests, since most of the tree sat in the ram after insertion.



High jump around 220 keys is likely a place, where node size becomes bing enough, and amount of them is small enough, so that total tree started to fit the page cache. In some cases there is no such a peak and graph slowly moves to around 40k insertions per second, which likely happens when some background task is actively using page cache flushing away test file's pages from the memory.

/devel/fs :: Link / Comments (0)

Comments are closed for this story.