Re: [boost] [BTREE] Get BTREE library into boost - Market Research

Subject: Re: [boost] [BTREE] Get BTREE library into boost - Market Research
From: Beman Dawes (bdawes_at_[hidden])
Date: 2012-12-21 17:32:08

On Fri, Dec 21, 2012 at 11:56 AM, Cory Nelson <phrosty_at_[hidden]> wrote:
> On Fri, Dec 21, 2012 at 2:26 AM, Rutger ter Borg <rutger_at_[hidden]> wrote:

> It's been some time since I've taken a look at Beman's btree code, so
> if I'm wrong about something please correct me.
>
> There is no support for variable-length keys at the moment. The code
> is structured to always have the same number of keys in one page.
> Compression would throw this off, adding a good bit of complexity.

Yes. To be a bit more specific, the same *maximum* number of keys on a page.

My implementation uses the same page size for both branch and leaf
pages, so the maximum number may differ between branch and leaf pages.

> Also, I believe the pages are kept in a blittable format (i.e. you can
> mmap it and use it right away without any deserializing), so there's a
> relatively minor complexity of changing that.

Yes.

> I do see a use for compression, and I'd definitely like the option.
> Not necessarily prefix/suffix folding, but a general (ie. zlib) page
> compression could come in handy on e.g. phones and SD cards, or over a
> network -- scenarios where I/O is particularly expensive and CPU is
> plentiful.

That's an interesting point!

If the cost of data transmission + cost of decompression of a
compressed page was less that the cost of data transmission of an
uncompressed page, compression would appear to make sense. But if
transmission is that slow, an even better approach might be to just
send the search key, do the search on the server, and return the found
data only.

Thanks,

--Beman