directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lécharny <elecha...@gmail.com>
Subject Re: [Mavibot] Transactions & troubles...
Date Sun, 22 Dec 2013 07:57:59 GMT
Le 12/20/13 9:21 AM, Emmanuel Lécharny a écrit :
> After a second thought, it might be simpler to use 2 tables to store the
> references to the current BTrees and to the modified btrees. 

This second thought was palin wrong. We *need* a tree of btrees,
otherwise we won't be able to keep old revisions (we have to be able to
retreive a previous version of a btree for wich the root page has been
swapped out, and we can only do that if we have a btree of btrees).


This btree of btrees will store references to btrees offset associated
with a btree name and a revision :

<<name, revision>, btree offset>

Here is the new diagram :

   Mavibot header
 +---------------------------------------+
 | PageIO size                           |
 +---------------------------------------+
 | number of managed btrees              |
 +---------------------------------------+
 | offset of the current btree of btrees |--+
 +---------------------------------------+   \
 | offset of the new btree of btrees     |----)------------+
 +---------------------------------------+   /             |
                                            |              |
                +---------------------------+              |
                |                                          |
                V                                          V
           Btree Header                               Btree Header   
       +------------------+                       +------------------+
       | revision         |                       | revision         |
       +------------------+                       +------------------+
       | nbElems          |                       | nbElems         
|                  
       +------------------+                       +------------------+
       | rootPage offset  |---+                   | rootPage offset  |---+
       +------------------+   |                   +------------------+   |
       | pageSize         |   |                   | pageSize         |   |
       +------------------+   |                   +------------------+   |
       | btree name       |   |                   | btree name       |   |
       +------------------+   |                   +------------------+   |
       | key serializer   |   |                   | key serializer   |   |
       +------------------+   |                   +------------------+   |
       | value serializer |   |                   | value serializer |   |
       +------------------+   |                   +------------------+   |
       | dups allowed     |   |                   | dups allowed     |   |
       +------------------+   |                   +------------------+   |
                              |                                          |
                              |                                          .
                              +                                          +
                             / \                                        . .
                            /   \                                      .   .
                           /     \                                   
.     .
                          /       \
                         /         \
                        /           \
                       /             \
                      /               \
                     /                 \
                    /                   \
                   +                     +
                   |                     |
                   V                     V
                 Node                  Leaf
          +-----------------+  +-------------------+
          | revision        |  | revision          |
          +-----------------+  +-------------------+
          | nbElems         |  | nbElems           |
          +-----------------+  +-------------------+
          | dataSize        |  | dataSize          |
          +-----------------+  +-------------------+
          | child[0]        |  | value[0] length   |
          +-----------------+  +-------------------+
          | key[0] length   |  | value[0]          |---> Btree 1
          +-----------------+  +-------------------+
          | key[0]          |  | key[0] length     |
          +-----------------+  +-------------------+
          | child[1]        |  | key[0]            |
          +-----------------+  +-------------------+
          | key[1] length   |  | value[1] length   |
          +-----------------+  +-------------------+
          | key[1]          |  | value[1]          |---> Btree 2
          +-----------------+  +-------------------+
          |         .       |  | key[1] length     |
          |         .       |  +-------------------+
          |         .       |  | key[1]            |
          +-----------------+  +-------------------+
          | child[N-1]      |  |         .         |
          +-----------------+  |         .         |
          | key[N-1] length |  |         .         |
          +-----------------+  +-------------------+
          | key[N-1]        |  | value[N-1] length |
          +-----------------+  +-------------------+
          | child[N]        |  | value[N-1]        |---> Btree 3
          +-----------------+  +-------------------+
                               | key[N-1] length   |
                               +-------------------+
                               | key[N-1]          |
                               +-------------------+


-- 
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com 


Mime
View raw message