Hello, On Wed, Sep 15, 2010 at 10:41 PM, Roland Bock wrote:

On 09/15/2010 06:04 PM, Beman Dawes wrote:

A Boost B-tree library would provide disk-based associative containers that scale all the way from really, really, small to really, really, large. B-trees perform well on hardware ranging from ancient floppy disk drives all the way up to humongous disk arrays. They are the technology behind most high-performance disk file systems and databases.

Any interest?

--Beman _______________________________________________

The documentation says "Types supplied by the Key and T template parameters must be memcpyable".

So I guess I could not use a nested btree like this

btree >

How about using regular b-tree and an allocator that gives you memory from a memory mapped file. More like boost::intrusive. For ACID properties, we are using BerkeleyDB 4.8+ which has an STL interface to hash/btree/recno/queue data structures on disk. Since BerkeleyDB is not free for commercial use, there is Tokyo Cabinet but lacks STL interface. IMHO, a good GSoc project would be to provide an STL interface to Tokyo Cabinet. With that, there will be a good alternative to BerkeleyDB based on LGPL (as Tokyo Cabinet is LGPL). -dhruva PS: I do not have any personal stake in either BerkeleyDB or Tokyo Cabinet. Just looking for a good alternative that I can develop expertise on and use it.

On Wed, Sep 15, 2010 at 7:26 PM, Cory Nelson wrote:

- Is concurrent access okay if it's opened as read-only?

Yes, as long as the file isn't being written by a different instance.

- Right now it's using synchronous I/O.  Can async support (via asio) be added?

I don't know the answer to that. I would need help from someone who understands async I/O far better than I do.

 How about memory-mapped I/O for small B-trees or large address spaces?

I've did some preliminary investigation about five years ago, and memory-mapped I/O looked like it might be cost effective. But I'd give it a lower priority than adding support for variable length keys/mapped_types or concurrency.

- Will this support multiple B-trees in one file?

Not currently. That would be relatively easy to support. What is the motivating use case?

- Will this implement ACID properties?

No. The model is a standard library associative container, not a database. ACID properties can be built on top of B-trees, but the B-trees themselves don't have ACID properties, other than a few aspects like atomic writes.

- Can this be adapted for in-memory use as well, with full non-POD support?

No current plans for that. Why wouldn't you just a standard library associative container for that? Cheers, --Beman

On Wed, Sep 15, 2010 at 10:40 PM, Cory Nelson wrote:

On Wed, Sep 15, 2010 at 6:08 PM, Beman Dawes wrote:

...

On Wed, Sep 15, 2010 at 7:26 PM, Cory Nelson wrote:

...

- Will this support multiple B-trees in one file?

Not currently. That would be relatively easy to support. What is the motivating use case?

Just ease of distribution, really.

I'm currently using a SQLite database to distribute a few tables of read-only data that doesn't need SQL, relational, or ACID properties -- it's just the best thing available in terms of ease of distribution and portability.  I'd love to remove all the unneeded layers and just use a B-tree directly.

Sounds quite useful. I can think of several past apps that would have benefited. I've added this to the Wish List: Multiple B-trees in one file. Requested by Cory Nelson. Possible design: Initial btree_map in the file is an index of its children. Key: name, Data: page id of the child's header page. Recursion allowed; the header page pointed could itself be an index header. Current interface might gain additional constructor and open() overload taking a ref to the parent index and the desired name.

...

...

- Will this implement ACID properties?

No. The model is a standard library associative container, not a database. ACID properties can be built on top of B-trees, but the B-trees themselves don't have ACID properties, other than a few aspects like atomic writes.

Alright, that clears up my understanding about the scope of this. Still sounds great!

...

...

- Can this be adapted for in-memory use as well, with full non-POD support?

No current plans for that. Why wouldn't you just a standard library associative container for that?

Storing keys together improves cache usage a lot for small keys, and allows the CPU to detect ordered iteration to prefetch the next cache line.  It also reduces fragmentation and the maximum number of pages that must be touched to find a result, which in turn reduces TLB misses and page faults.  The tests here indicate that this can be very significant with large collections:

That's also the point made by the article Thorsten referenced, http://queue.acm.org/detail.cfm?id=1814327, although it is claiming much greater speedups IIRC.

http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.htm...

Interesting. So someone has already done the work for drop in STL associative container replacements. The timings only covered small trees. 16,000 was the number of elements mentioned. I'm testing with up to 100 million elements, and plan to expand that to a few billion elements. Thanks, --Beman

2010/9/16 Ion Gaztañaga :

El 16/09/2010 3:08, Beman Dawes escribió:

...

...

- Can this be adapted for in-memory use as well, with full non-POD support?

No current plans for that. Why wouldn't you just a standard library associative container for that?

I think it's about performance/node overhead (less rebalances, you allocate arrays and not individual nodes). But for memory, T-Trees are the way to go. They are used by many in-memory DBs.

http://en.wikipedia.org/wiki/T-tree

"In computer science a T-tree is a type of binary tree data structure that is used by main-memory databases, such as Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen and KairosMobileLite"

Correct me if I'm wrong, but it looks like a T-tree is just a plain binary tree where the data is referenced with pointers and not stored in the tree -- so it's designed to be memory-efficient when the key is larger than a pointer and is already stored elsewhere. Useful for databases that want low-overhead (in terms of key size, not tree implementation) indexes into tables. If that's the case, then it is not applicable here. -- Cory Nelson http://int64.org