Re: [boost] Interest in B-tree library for Boost?

Subject: Re: [boost] Interest in B-tree library for Boost?
From: Cory Nelson (phrosty_at_[hidden])
Date: 2010-09-23 14:31:11

On Tue, Sep 21, 2010 at 3:25 PM, Beman Dawes <bdawes_at_[hidden]> wrote:
> How do SQLlite or other libraries provide safety against another
> thread crashing? Do they actually stop the other threads until the
> b-tree modification completes, have some form of recovery, or some
> other approach? Do they have protection against another process
> corrupting the B-tree?

I believe this is how it's done:

1) Put any changes into new or free pages -- don't ever overwrite any old data.

2) Write a list of "free" page indexes -- the indexes of the header
and ones that (1) replaced.

3) Fsync.

4) Write a new header to the end of the file.

5) Fsync.

If you start an operation and a valid header isn't found at the end of
the file, just read in reverse until you find one.  This necessitates
extra code to encapsulate multiple operations in transactions, because
fsync is expensive.  You still need to maintain a reader-writer lock
on top of the file.

-- 
Cory Nelson
http://int64.org