[CONF] Apache Labs > Data structure

[confluence]

Data structure Page edited by Emmanuel Lécharny Changes (9) ... h2. Page/Leaf/Node We will distinguish a Node from a Leaf : a Leaf contains values, when a Node contains references to some other pages. Also leaves are linked together, when Nodes are not. We will distinguish a _Node_ from a _Leaf_ : a _Leaf_ contains values, when a _Node_ contains references to some other pages. Also leaves are linked together, when nodes are not. We will design an interface (+Page+), and abstract class (+AbstractPage+), and two implementations (+Node+ and +Leaf+). We will design an interface (_Page_), and abstract class (_AbstractPage_), and two implementations (_Node_ and _Leaf_). Here is the class diagram : ... !PageHierarchy.png|border=1! h3. AbstractPage We gather all the shared fields used by _Node_ and _Leaf_ classes here. Basically, we store the keys, a reference to the _BTree_+, the page identifier and the underlying physical page ID, the revision, and the number of keys in the page. This is pretty much it. Here is a description of the class : !abstractPage.png|border=1! h3. Node A _Node_ contains the keys, the references to its children and some internal values. Here is the class : !Node.png|border=1! h3. Leaf h3. AbstractPage The Leaf contains the values, and some pointers to the previous _Leaf_ and tto the next _Leaf_. Here is the class : !Leaf.png|border=1! h1. Helper classes ... Full Content We will now define the needed data structure here. Base data structure BTree Page/Leaf/Node We will distinguish a Node from a Leaf : a Leaf contains values, when a Node contains references to some other pages. Also leaves are linked together, when nodes are not. We will design an interface (Page), and abstract class (AbstractPage), and two implementations (Node and Leaf). Here is the class diagram : AbstractPage We gather all the shared fields used by Node and Leaf classes here. Basically, we store the keys, a reference to the BTree+, the page identifier and the underlying physical page ID, the revision, and the number of keys in the page. This is pretty much it. Here is a description of the class : Node A Node contains the keys, the references to its children and some internal values. Here is the class : Leaf The Leaf contains the values, and some pointers to the previous Leaf and tto the next Leaf. Here is the class : Helper classes InsertResult/ModifyResult/SplitResult Change Notification Preferences View Online | View Changes | Add Comment --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@labs.apache.org For additional commands, e-mail: commits-h...@labs.apache.org