directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From build...@apache.org
Subject svn commit: r908536 - in /websites/staging/directory/trunk/content: ./ mavibot/user-guide/4-btree-operations.html
Date Sat, 10 May 2014 15:19:08 GMT
Author: buildbot
Date: Sat May 10 15:19:08 2014
New Revision: 908536

Log:
Staging update by buildbot for directory

Modified:
    websites/staging/directory/trunk/content/   (props changed)
    websites/staging/directory/trunk/content/mavibot/user-guide/4-btree-operations.html

Propchange: websites/staging/directory/trunk/content/
------------------------------------------------------------------------------
--- cms:source-revision (original)
+++ cms:source-revision Sat May 10 15:19:08 2014
@@ -1 +1 @@
-1593561
+1593703

Modified: websites/staging/directory/trunk/content/mavibot/user-guide/4-btree-operations.html
==============================================================================
--- websites/staging/directory/trunk/content/mavibot/user-guide/4-btree-operations.html (original)
+++ websites/staging/directory/trunk/content/mavibot/user-guide/4-btree-operations.html Sat
May 10 15:19:08 2014
@@ -185,14 +185,14 @@ returned).</p>
 <h4 id="4124-prev">4.1.2.4 prev</h4>
 <p>Moves to the previous value of the current key or to the previous key if all the
values of the current key have been processed, and return the associated tuple.</p>
 <h2 id="42-browse-operations">4.2 Browse Operations</h2>
-<p>Now that we know what a <em>Cursor</em> is about, we can describe the
various <em>browse</em> operations that can be applied on a <em>BTree</em>.</p>
+<p>Now that we know what a <em>Cursor</em> is about, we can describe the
various <em>browse</em> operations that can be applied on a <em>B-tree</em>.</p>
 <h3 id="421-btreebrowse">4.2.1 BTree.browse()</h3>
-<p>This method returns a cursor with the position set before the first element of the
<strong>B-tree</strong>, for the current revision. It returns a <em>TupleCursor</em>
that contain the tuples <key,value> present in the <em>Btree</em>.</p>
-<p>Assuming you have an existing <em>BTree</em>, using this method is quite
straigthforward. Here is an example with a persisted <em>BTree</em>  :</p>
-<div class="codehilite"><pre>    <span class="o">//</span> <span
class="n">Create</span> <span class="n">a</span> <span class="n">RecordManager</span>
<span class="n">that</span> <span class="n">will</span> <span class="n">contain</span>
<span class="n">the</span> <span class="n">BTree</span>
+<p>This method returns a cursor with the position set before the first element of the
<strong>B-tree</strong>, for the current revision. It returns a <em>TupleCursor</em>
that contain the tuples <key,value> present in the <em>B-tree</em>.</p>
+<p>Assuming you have an existing <em>B-tree</em>, using this method is
quite straigthforward. Here is an example with a persisted <em>B-tree</em>  :</p>
+<div class="codehilite"><pre>    <span class="o">//</span> <span
class="n">Create</span> <span class="n">a</span> <span class="n">RecordManager</span>
<span class="n">that</span> <span class="n">will</span> <span class="n">contain</span>
<span class="n">the</span> <span class="n">B</span><span class="o">-</span><span
class="n">tree</span>
     <span class="n">RecordManager</span> <span class="n">recordManager</span>
<span class="p">=</span> <span class="n">new</span> <span class="n">RecordManager</span><span
class="p">(</span> &quot;<span class="n">Test</span><span class="p">.</span><span
class="n">db</span>&quot; <span class="p">);</span>
 
-    <span class="o">//</span> <span class="n">Create</span> <span
class="n">a</span> <span class="n">BTree</span> <span class="n">to</span>
<span class="n">play</span> <span class="n">with</span>
+    <span class="o">//</span> <span class="n">Create</span> <span
class="n">a</span> <span class="n">B</span><span class="o">-</span><span
class="n">tree</span> <span class="n">to</span> <span class="n">play</span>
<span class="n">with</span>
     <span class="n">BTree</span><span class="o">&lt;</span><span
class="n">Long</span><span class="p">,</span> <span class="n">String</span><span
class="o">&gt;</span> <span class="n">btree</span> <span class="p">=</span>
<span class="n">recordManager</span><span class="p">.</span><span
class="n">addBTree</span><span class="p">(</span> &quot;<span
class="n">test</span>&quot;<span class="p">,</span> <span class="n">LongSerializer</span><span
class="p">.</span><span class="n">INSTANCE</span><span class="p">,</span>
<span class="n">StringSerializer</span><span class="p">.</span><span
class="n">INSTANCE</span><span class="p">,</span> <span class="n">true</span>
<span class="p">);</span>
 
     <span class="o">//</span> <span class="n">Inject</span> <span
class="n">some</span> <span class="n">data</span>
@@ -235,11 +235,11 @@ returned).</p>
 <h3 id="422-btreebrowse-long">4.2.2 BTree.browse( long )</h3>
 <p>This method returns a cursor with the position set before the first element of the
<strong>B-tree</strong>, for the given revision. </p>
 <p>Here, the big difference is that you can fetch some data from an older revision
- assuming this revision is still present, of course -.</p>
-<p>It returns a <em>TupleCursor</em> that contain the tuples <key,value>
present in the <em>Btree</em>.</p>
+<p>It returns a <em>TupleCursor</em> that contain the tuples <key,value>
present in the <em>B-tree</em>.</p>
 <p>You can use the exact same code than for the <em>browse()</em> method,
except that you have to pass the version you want to browse.</p>
 <h3 id="423-btreebrowsefrom-k-key">4.2.3 BTree.browseFrom( K key )</h3>
 <p>This method returns a cursor with the position set before the given key of the <strong>B-tree</strong>.
If the key does not exist, the cursor will be set to the closest lower value (or upper value
if it's lower than the lowest value)</p>
-<p>It returns a <em>TupleCursor</em> that contain the tuples <key,value>
present in the <em>Btree</em>.</p>
+<p>It returns a <em>TupleCursor</em> that contain the tuples <key,value>
present in the <em>B-tree</em>.</p>
 <p>You can use the exact same code than for the <em>browse()</em> method.
Here is an example, where we start after the latest present key :</p>
 <div class="codehilite"><pre>    <span class="o">//</span> <span
class="n">Inject</span> <span class="n">some</span> <span class="n">data</span>
     <span class="k">for</span> <span class="p">(</span> <span
class="n">long</span> <span class="nb">i</span> <span class="p">=</span>
0<span class="p">;</span> <span class="nb">i</span> <span class="o">&lt;</span><span
class="p">=</span> 1000<span class="n">L</span><span class="p">;</span>
<span class="nb">i</span> <span class="o">+</span><span class="p">=</span>
2 <span class="p">)</span>
@@ -257,31 +257,118 @@ returned).</p>
 
 
 <h3 id="424-btreebrowsefrom-long-revision-k-key">4.2.4 BTree.browseFrom( long revision,
K key )</h3>
-<p>TODO</p>
+<p>This method can be used when one want to browse a <em>B-tree</em> starting
from a given key, for a specific revision of a <em>B-tree</em>. The only difference
with the <em>BTree.browseFrom( K )</em> method is the <em>B-tree</em>
revision which is provided.</p>
 <h2 id="43-contains-operations">4.3 Contains Operations</h2>
+<p>We have a couple of methods that can be used to know if some tuple <em><Key,
Value></em> is present in a <em>B-tree</em>.</p>
 <h3 id="431-btreecontains-k-key-v-value">4.3.1 BTree.contains( K key, V value )</h3>
-<p>TODO</p>
+<p>This method checks if a <em>B-tree</em> contains a tuple <em><key,
value></em>. As a key might have more than one value, we test the tuple. If one wants
to check if a key is present, regardless of the value, the <em>hasKey()</em> method
should be used.</p>
+<p>Here is an example where the <em>contains()</em> method is used :</p>
+<div class="codehilite"><pre><span class="p">...</span>
+<span class="n">boolean</span> <span class="n">result</span> <span
class="p">=</span> <span class="n">btree</span><span class="p">.</span><span
class="n">contains</span><span class="p">(</span> 1<span class="n">L</span><span
class="p">,</span> &quot;<span class="n">V1</span>&quot; <span
class="p">);</span>
+<span class="p">...</span>
+</pre></div>
+
+
+<p>If the <em>B-tree</em> contains the &lt;1L, "V1"&gt; tuple,
then the method will return true, false otherwise.</p>
 <h3 id="432-btreecontains-long-revision-k-key-v-value">4.3.2 BTree.contains( long revision,
K key, V value )</h3>
-<p>TODO</p>
-<h2 id="44-has-operations">4.4 Has Operations</h2>
+<p>This is the same method that the previous one, except that it's applied on a specific
revision of a <em>B-tree</em>. The first parameter is the revision.</p>
+<h2 id="44-haskey-operations">4.4 HasKey Operations</h2>
+<p>We have some specific methods that check the presence of a key in a <em>B-tree</em>.
There are described below.</p>
 <h3 id="441-btreehaskey-k-key">4.4.1 BTree.hasKey( K key )</h3>
-<p>TODO</p>
+<p>The <em>hasKey(K key)</em> method check the presence of the given <em>key</em>
in the current <em>B-tree</em>. If it's present, this method returns <em>true</em>,
otherwise it returns <em>false</em>. Here is an example of usage :</p>
+<div class="codehilite"><pre><span class="p">...</span>
+<span class="n">boolean</span> <span class="n">result</span> <span
class="p">=</span> <span class="n">btree</span><span class="p">.</span><span
class="n">hasKey</span><span class="p">(</span> 1<span class="n">L</span>
<span class="p">);</span>
+<span class="p">...</span>
+</pre></div>
+
+
 <h3 id="442-btreehaskey-long-revision-k-key">4.4.2 BTree.hasKey( long revision, K key
)</h3>
-<p>TODO</p>
+<p>The exact same method, but applied to a given revision of the <em>B-tree</em>.</p>
 <h2 id="45-get-operations">4.5 Get Operations</h2>
+<p>Instead of browsing the <em>B-tree</em>, one can get the values associated
with a key in a simple operation. The big difference is that it's not then possible to move
forward or backward in the <em>B-tree</em> from the retrieved value.</p>
 <h3 id="451-btreeget-k-key">4.5.1 BTree.get( K key )</h3>
-<p>TODO</p>
+<p>This method get the value associated to the given key, if it exists. If the key
does not exist, then a <em>KeyNotFoundException</em> is thrown by the method.</p>
+<DIV class="note" markdown="1">
+It's important to understand that, as a <i>B-tree</i> can have multiple values,
the <i>get(K)</i> method will <b>NOT</b> return all the values, but
the very first one. If one wants to get all the values for a given key, the <i>BTree.getValues(K)</i>
has te be used instead.
+</DIV>
+
+<p>Here is an example :</p>
+<div class="codehilite"><pre><span class="p">...</span>
+<span class="k">try</span>
+<span class="p">{</span>
+    <span class="n">String</span> <span class="n">value</span> <span
class="p">=</span> <span class="n">btree</span><span class="p">.</span><span
class="n">get</span><span class="p">(</span> 1<span class="n">L</span>
<span class="p">);</span> <span class="o">//</span> <span class="n">Will</span>
<span class="k">return</span> &quot;<span class="n">V1</span>&quot;
+    <span class="p">...</span>
+    <span class="o">//</span> <span class="n">process</span> <span
class="n">teh</span> <span class="n">found</span> <span class="n">value</span>
+<span class="p">}</span>
+<span class="k">catch</span> <span class="p">(</span> <span class="n">KeyNotFoundException</span>
<span class="n">knfe</span> <span class="p">)</span>
+<span class="p">{</span>
+    <span class="o">//</span> <span class="n">deal</span> <span
class="n">with</span> <span class="n">the</span> <span class="n">exception</span>
+<span class="p">}</span>
+<span class="p">...</span>
+</pre></div>
+
+
 <h3 id="452-btreeget-long-revision-k-key">4.5.2 BTree.get( long revision, K key )</h3>
-<p>TODO</p>
+<p>Same method than previously, but with a provided <em>B-tree</em> revision.</p>
 <h3 id="453-btreegetvalues-k-key">4.5.3 BTree.getValues( K key )</h3>
-<p>TODO</p>
+<p>One should use this method to get all the values assocatied with a key. This method
returns  a <em>ValueCursor</em>, which allows the user to browse the various values.
The cursor is set before the first value.</p>
+<p>Here is an example that shows how to use this method :</p>
+<div class="codehilite"><pre><span class="p">...</span>
+<span class="o">//</span> <span class="n">The</span> <span class="n">key</span>
1<span class="n">L</span> <span class="n">is</span> <span class="n">associated</span>
<span class="n">with</span> <span class="p">{</span>&quot;<span
class="n">V1</span>&quot;<span class="p">,</span> &quot;<span
class="n">V2</span>&quot;<span class="p">,</span> &quot;<span
class="n">V3</span>&quot;<span class="p">}</span>
+<span class="n">ValueCursor</span><span class="o">&lt;</span><span
class="n">String</span><span class="o">&gt;</span> <span class="n">values</span>
<span class="p">=</span> <span class="n">dupsTree</span><span class="p">.</span><span
class="n">getValues</span><span class="p">(</span> 1<span class="n">L</span><span
class="p">);</span>
+
+<span class="k">while</span> <span class="p">(</span> <span class="n">values</span><span
class="p">.</span><span class="n">hasNext</span><span class="p">()</span>
<span class="p">)</span>
+<span class="p">{</span>
+    <span class="n">System</span><span class="p">.</span><span
class="n">out</span><span class="p">.</span><span class="n">println</span><span
class="p">(</span> <span class="n">value</span><span class="p">.</span><span
class="n">next</span><span class="p">()</span> <span class="p">);</span>
+<span class="p">}</span>
+<span class="p">...</span>
+</pre></div>
+
+
+<p>This will produce the following output :</p>
+<div class="codehilite"><pre><span class="n">V1</span>
+<span class="n">V2</span>
+<span class="n">V3</span>
+</pre></div>
+
+
 <h2 id="46-insert-operation">4.6 Insert Operation</h2>
+<p>Inserting elements into a <em>B-tree</em> is as simple as to call the
<em>insert(K, V)</em> method. </p>
+<DIV class="note" markdown="1">
+It would be interesting to have an <i>insert</i> method that can take more than
one value. This might be added in one future version.
+</DIV>
+
+<p>If the key already exist, the value will be added, or replaced if the value already
exist keep in mind that we use a comparator when it comes to check a value existence, and
two different values may be seen as equal).</p>
+<p>Here is an exemple :</p>
+<div class="codehilite"><pre><span class="p">...</span>
+<span class="o">//</span> <span class="n">Insert</span> <span
class="n">a</span> <span class="n">new</span> <span class="n">key</span>
<span class="n">and</span> <span class="n">value</span> <span class="n">into</span>
<span class="n">a</span> <span class="n">B</span><span class="o">-</span><span
class="n">tree</span>
+<span class="o">//</span> <span class="n">The</span> <span class="n">old</span>
<span class="n">value</span> <span class="n">will</span> <span
class="n">be</span> <span class="n">returned</span> <span class="k">if</span>
<span class="n">we</span> <span class="n">already</span> <span
class="n">have</span> <span class="n">a</span> &quot;<span class="n">V3</span>&quot;
<span class="n">in</span> <span class="n">the</span> <span class="n">B</span><span
class="o">-</span><span class="n">tree</span>
+<span class="n">String</span> <span class="n">oldValue</span> <span
class="p">=</span> <span class="n">btree</span><span class="p">.</span><span
class="n">insert</span><span class="p">(</span> 3<span class="n">L</span><span
class="p">,</span> &quot;<span class="n">V3</span>&quot; <span
class="p">);</span>
+<span class="p">...</span>
+</pre></div>
+
+
+<DIV class="note" markdown="1">
+One can only add one single value if the <i>B-tree</i> does not accept duplicate
values. In this case, the <i>insert()</i> method will throw a <i>DuplicateValueNotAllowedException</i>
exception.
+</DIV>
+
+<p>If the <em>B-tree</em> accepts multiple values for a key, one can write
such code :</p>
+<div class="codehilite"><pre><span class="p">...</span>
+<span class="o">//</span> <span class="n">Insert</span> <span
class="n">a</span> <span class="n">new</span> <span class="n">key</span>
<span class="n">and</span> <span class="n">value</span> <span class="n">into</span>
<span class="n">a</span> <span class="n">B</span><span class="o">-</span><span
class="n">tree</span>
+<span class="n">btree</span><span class="p">.</span><span class="n">insert</span><span
class="p">(</span> 1<span class="n">L</span><span class="p">,</span>
&quot;<span class="n">V1</span>&quot; <span class="p">);</span>
+<span class="n">btree</span><span class="p">.</span><span class="n">insert</span><span
class="p">(</span> 1<span class="n">L</span><span class="p">,</span>
&quot;<span class="n">V2</span>&quot; <span class="p">);</span>
+<span class="n">btree</span><span class="p">.</span><span class="n">insert</span><span
class="p">(</span> 1<span class="n">L</span><span class="p">,</span>
&quot;<span class="n">V3</span>&quot; <span class="p">);</span>
+<span class="o">//</span> <span class="n">At</span> <span class="n">this</span>
<span class="n">point</span><span class="p">,</span> <span class="n">the</span>
<span class="n">key</span> 1<span class="n">L</span> <span class="n">will</span>
<span class="n">be</span> <span class="n">associated</span> <span
class="n">with</span> <span class="p">{</span><span class="n">V1</span><span
class="p">,</span> <span class="n">V2</span><span class="p">,</span>
<span class="n">V3</span><span class="p">}</span>
+<span class="p">...</span>
+</pre></div>
+
+
 <h2 id="47-delete-operations">4.7 Delete Operations</h2>
 <h3 id="481-btreedelete-k-key">4.8.1 BTree.delete( K key )</h3>
 <p>TODO</p>
 <h3 id="472-btreedelete-k-key-v-value">4.7.2 BTree.delete( K key, V value )</h3>
 <p>TODO</p>
-<h2 id="48-other-btree-operations">4.8 Other BTree operations</h2>
+<h2 id="48-other-b-tree-operations">4.8 Other B-tree operations</h2>
 <h3 id="481-btreeclose">4.8.1 BTree.close()</h3>
 <p>TODO</p>
 <h3 id="482-btreeflush">4.8.2 BTree.flush()</h3>



Mime
View raw message