You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by bu...@apache.org on 2013/12/21 10:26:41 UTC
svn commit: r891336 - in /websites/staging/directory/trunk/content: ./
mavibot/user-guide/
Author: buildbot
Date: Sat Dec 21 09:26:40 2013
New Revision: 891336
Log:
Staging update by buildbot for directory
Modified:
websites/staging/directory/trunk/content/ (props changed)
websites/staging/directory/trunk/content/mavibot/user-guide/1.1-btree-basics.html
websites/staging/directory/trunk/content/mavibot/user-guide/2-btree-types.html
websites/staging/directory/trunk/content/mavibot/user-guide/3-btree-management.html
websites/staging/directory/trunk/content/mavibot/user-guide/4-btree-operations.html
websites/staging/directory/trunk/content/mavibot/user-guide/5-btree-informations.html
websites/staging/directory/trunk/content/mavibot/user-guide/6-btree-configuration.html
Propchange: websites/staging/directory/trunk/content/
------------------------------------------------------------------------------
--- cms:source-revision (original)
+++ cms:source-revision Sat Dec 21 09:26:40 2013
@@ -1 +1 @@
-1552775
+1552893
Modified: websites/staging/directory/trunk/content/mavibot/user-guide/1.1-btree-basics.html
==============================================================================
--- websites/staging/directory/trunk/content/mavibot/user-guide/1.1-btree-basics.html (original)
+++ websites/staging/directory/trunk/content/mavibot/user-guide/1.1-btree-basics.html Sat Dec 21 09:26:40 2013
@@ -17,7 +17,7 @@
-->
<html>
<head>
- <title>1.1 - BTree Basics — Apache Directory</title>
+ <title>1.1 - B-tree Basics — Apache Directory</title>
<link href="./../../css/common.css" rel="stylesheet" type="text/css">
<link href="./../../css/turquoise.css" rel="stylesheet" type="text/css">
@@ -144,14 +144,24 @@
</div>
<div class="nav_next">
- <a href="2-btree-types.html">2 - BTree Types</a>
+ <a href="2-btree-types.html">2 - B-tree Types</a>
</div>
<div class="clearfix"></div>
</div>
-<h1 id="11-btree-basics">1.1 - BTree Basics</h1>
+<h1 id="11-b-tree-basics">1.1 - B-tree Basics</h1>
+<p>A <strong>B-tree</strong> "tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time." (see <a href="http://en.wikipedia.org/wiki/B-tree">Wikipedia</a>)</p>
+<p>The important point here is the last one : it guarantees <strong>O(logn)</strong> operations, compared to any other data structures (a hashed data structure offers <strong>O(n)</strong> average operations, but can degenerate to <strong>O(n2)</strong>, and ordering is not kept. </p>
+<p><strong>B-trees</strong> are everywhere : databases, OS, etc. It's a critical data structure when you are to deal with a huge number of data.</p>
+<p>1.1.1 - Inside a B-tree</p>
+<p>A <strong>B-Tree</strong> contains <strong>Nodes</strong> and <strong>Leaves</strong>. A <em>Node</em> points to other <strong>Nodes</strong> or <strong>Leaves</strong>. <strong>Leaves</strong> contains <strong>Values</strong>. Both <strong>Nodes</strong> and <strong>Leaves</strong> have <strong>Keys</strong> that are associated with <em>Values</em>.</p>
+<p>Pretty simple !</p>
+<p>One last thing : <strong>Keys</strong> are ordered, and this is the condition for the easy and fast retrieval of <strong>Values</strong>.</p>
+<p>A few more rules are enforced :
+<em> A <strong>Node</strong> and a <strong>Leaf</strong> contains up to N values (N being generally a power of 2, so 2, 4, 8, 16...).
+</em> You can't have less than N/2 <strong>Values</strong> or <strong>keys</strong> in a <strong>Leaf</strong> or a <strong>Node</strong>, except for the root <strong>Node</strong>.</p>
<div class="nav">
@@ -167,7 +177,7 @@
</div>
<div class="nav_next">
- <a href="2-btree-types.html">2 - BTree Types</a>
+ <a href="2-btree-types.html">2 - B-tree Types</a>
</div>
<div class="clearfix"></div>
Modified: websites/staging/directory/trunk/content/mavibot/user-guide/2-btree-types.html
==============================================================================
--- websites/staging/directory/trunk/content/mavibot/user-guide/2-btree-types.html (original)
+++ websites/staging/directory/trunk/content/mavibot/user-guide/2-btree-types.html Sat Dec 21 09:26:40 2013
@@ -17,7 +17,7 @@
-->
<html>
<head>
- <title>2 - BTree Types — Apache Directory</title>
+ <title>2 - B-tree Flavors — Apache Directory</title>
<link href="./../../css/common.css" rel="stylesheet" type="text/css">
<link href="./../../css/turquoise.css" rel="stylesheet" type="text/css">
@@ -134,7 +134,7 @@
<div class="nav">
<div class="nav_prev">
- <a href="1.1-btree-basics.html">1.1 - BTree Basics</a>
+ <a href="1.1-btree-basics.html">1.1 - B-tree Basics</a>
</div>
<div class="nav_up">
@@ -144,21 +144,26 @@
</div>
<div class="nav_next">
- <a href="3-btree-management.html">3 - BTree management</a>
+ <a href="3-btree-management.html">3 - Mavibot B-tree management</a>
</div>
<div class="clearfix"></div>
</div>
-<h1 id="2-btree-types">2 - BTree Types</h1>
-<p>TODO</p>
+<h1 id="2-b-tree-flavors">2 - B-tree flavors</h1>
+<p>You have many different flavors of <strong>B-trees</strong> :</p>
+<ul>
+<li>B+tree : we have a pointer to the next <strong>Node</strong> in each <strong>Node</strong></li>
+<li>B*-tree : the internal <strong>Nodes</strong> are compacted, to contain at least 2/3 of the number of possible slots</li>
+<li>Counted B*-tree : the <strong>B-tree</strong></li>
+</ul>
<div class="nav">
<div class="nav_prev">
- <a href="1.1-btree-basics.html">1.1 - BTree Basics</a>
+ <a href="1.1-btree-basics.html">1.1 - B-tree Basics</a>
</div>
<div class="nav_up">
@@ -168,7 +173,7 @@
</div>
<div class="nav_next">
- <a href="3-btree-management.html">3 - BTree management</a>
+ <a href="3-btree-management.html">3 - Mavibot B-tree management</a>
</div>
<div class="clearfix"></div>
Modified: websites/staging/directory/trunk/content/mavibot/user-guide/3-btree-management.html
==============================================================================
--- websites/staging/directory/trunk/content/mavibot/user-guide/3-btree-management.html (original)
+++ websites/staging/directory/trunk/content/mavibot/user-guide/3-btree-management.html Sat Dec 21 09:26:40 2013
@@ -17,7 +17,7 @@
-->
<html>
<head>
- <title>3 - BTree management — Apache Directory</title>
+ <title>3 - Mavibot B-tree management — Apache Directory</title>
<link href="./../../css/common.css" rel="stylesheet" type="text/css">
<link href="./../../css/turquoise.css" rel="stylesheet" type="text/css">
@@ -134,7 +134,7 @@
<div class="nav">
<div class="nav_prev">
- <a href="2-btree-types.html">2 - BTree types</a>
+ <a href="2-btree-types.html">2 - Mavibot B-tree types</a>
</div>
<div class="nav_up">
@@ -144,21 +144,21 @@
</div>
<div class="nav_next">
- <a href="4-btree-operations.html">4 - BTree operations</a>
+ <a href="4-btree-operations.html">4 - Mavibot B-tree operations</a>
</div>
<div class="clearfix"></div>
</div>
-<h1 id="3-btree-management">3 - BTree management</h1>
+<h1 id="3-mavibot-b-tree-management">3 - Mavibot B-tree management</h1>
<p>TODO</p>
<div class="nav">
<div class="nav_prev">
- <a href="2-btree-types.html">2 - BTree types</a>
+ <a href="2-btree-types.html">2 - Mavibot B-tree types</a>
</div>
<div class="nav_up">
@@ -168,7 +168,7 @@
</div>
<div class="nav_next">
- <a href="4-btree-operations.html">4 - BTree operations</a>
+ <a href="4-btree-operations.html">4 - Mavibot B-tree operations</a>
</div>
<div class="clearfix"></div>
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 Dec 21 09:26:40 2013
@@ -17,7 +17,7 @@
-->
<html>
<head>
- <title>4 - BTree operations — Apache Directory</title>
+ <title>4 - Mavibot B-tree operations — Apache Directory</title>
<link href="./../../css/common.css" rel="stylesheet" type="text/css">
<link href="./../../css/turquoise.css" rel="stylesheet" type="text/css">
@@ -134,7 +134,7 @@
<div class="nav">
<div class="nav_prev">
- <a href="3-btree-management.html">3 - BTree management</a>
+ <a href="3-btree-management.html">3 - Mavibot B-tree management</a>
</div>
<div class="nav_up">
@@ -144,23 +144,23 @@
</div>
<div class="nav_next">
- <a href="5-btree-informations.html">5 - BTree information</a>
+ <a href="5-btree-informations.html">5 - Mavibot B-tree information</a>
</div>
<div class="clearfix"></div>
</div>
-<h1 id="4-btree-operations">4 - BTree operations</h1>
-<p>We will now list all the possible operations that can be applied on a <strong>BTree</strong>. But first, let us understand the <em>Cursor</em> interface, as it is used for navigating a <strong>BTree</strong> using various types of <em>browse</em> operations.</p>
+<h1 id="4-mavibot-b-tree-operations">4 - Mavibot B-tree operations</h1>
+<p>We will now list all the possible operations that can be applied on a <strong>B-tree</strong>. But first, let us understand the <em>Cursor</em> interface, as it is used for navigating a <strong>B-tree</strong> using various types of <em>browse</em> operations.</p>
<h2 id="41-the-cursor-interface">4.1 The Cursor interface</h2>
-<p>All the <em>browse</em> operations will return a <em>Cursor</em> instance. A <em>Cursor</em> allows navigating forward and backward on a <strong>BTree</strong>. It starts at a specific position, and can be moved to a specific position too. The default position for a <em>Cursor</em> is before the very first element of the <strong>BTree</strong></p>
+<p>All the <em>browse</em> operations will return a <em>Cursor</em> instance. A <em>Cursor</em> allows navigating forward and backward on a <strong>B-tree</strong>. It starts at a specific position, and can be moved to a specific position too. The default position for a <em>Cursor</em> is before the very first element of the <strong>B-tree</strong></p>
<DIV class="note" markdown="1">
It is important to understand that a <b>Cursor</b> returns tuples, not keys. A Key may be associated with many values, so a cursor may return many tuples with a given key (each one will have a different value though).
</DIV>
-<p>Here is the <strong>BTree</strong> sample we will use for the following examples :</p>
-<p><img alt="Sample BTree" src="images/ug-btree-sample.png" /></p>
+<p>Here is the <strong>B-tree</strong> sample we will use for the following examples :</p>
+<p><img alt="Sample B-tree" src="images/ug-btree-sample.png" /></p>
<h3 id="411-cursor-position-management">4.1.1 Cursor position management</h3>
<h4 id="4111-afterlast">4.1.1.1 afterLast</h4>
<p>Moves the current position after the last element (last key and last value). The following schema shows the new position of the pointer after having called the <em>afterLast()</em> method :</p>
@@ -194,13 +194,13 @@ returned).</p>
<h2 id="41-browse-operations">4.1 Browse Operations</h2>
<p>Now that we know what a <em>Cursor</em> is about, we can describe the various <em>browse</em> operations.</p>
<h3 id="411-browse">4.1.1 browse()</h3>
-<p>This method returns a cursor with the position set before the first key of the <strong>BTree</strong>. </p>
+<p>This method returns a cursor with the position set before the first key of the <strong>B-tree</strong>. </p>
<div class="nav">
<div class="nav_prev">
- <a href="3-btree-management.html">3 - BTree management</a>
+ <a href="3-btree-management.html">3 - Mavibot B-tree management</a>
</div>
<div class="nav_up">
@@ -210,7 +210,7 @@ returned).</p>
</div>
<div class="nav_next">
- <a href="5-btree-informations.html">5 - BTree information</a>
+ <a href="5-btree-informations.html">5 - Mavibot B-tree information</a>
</div>
<div class="clearfix"></div>
Modified: websites/staging/directory/trunk/content/mavibot/user-guide/5-btree-informations.html
==============================================================================
--- websites/staging/directory/trunk/content/mavibot/user-guide/5-btree-informations.html (original)
+++ websites/staging/directory/trunk/content/mavibot/user-guide/5-btree-informations.html Sat Dec 21 09:26:40 2013
@@ -17,7 +17,7 @@
-->
<html>
<head>
- <title>5 - BTree information — Apache Directory</title>
+ <title>5 - Mavibot B-tree information — Apache Directory</title>
<link href="./../../css/common.css" rel="stylesheet" type="text/css">
<link href="./../../css/turquoise.css" rel="stylesheet" type="text/css">
@@ -134,7 +134,7 @@
<div class="nav">
<div class="nav_prev">
- <a href="4-btree-operations.html">4 - BTree operations</a>
+ <a href="4-btree-operations.html">4 - Mavibot B-tree operations</a>
</div>
<div class="nav_up">
@@ -144,21 +144,21 @@
</div>
<div class="nav_next">
- <a href="6-btree-configuration.html">6 - BTree configuration</a>
+ <a href="6-btree-configuration.html">6 - Mavibot B-tree configuration</a>
</div>
<div class="clearfix"></div>
</div>
-<h1 id="5-btree-information">5 - BTree information</h1>
+<h1 id="5-mavibot-b-tree-information">5 - Mavibot B-tree information</h1>
<p>TODO</p>
<div class="nav">
<div class="nav_prev">
- <a href="4-btree-operations.html">4 - BTree operations</a>
+ <a href="4-btree-operations.html">4 - Mavibot B-tree operations</a>
</div>
<div class="nav_up">
@@ -168,7 +168,7 @@
</div>
<div class="nav_next">
- <a href="6-btree-configuration.html">6 - BTree configuration</a>
+ <a href="6-btree-configuration.html">6 - Mavibot B-tree configuration</a>
</div>
<div class="clearfix"></div>
Modified: websites/staging/directory/trunk/content/mavibot/user-guide/6-btree-configuration.html
==============================================================================
--- websites/staging/directory/trunk/content/mavibot/user-guide/6-btree-configuration.html (original)
+++ websites/staging/directory/trunk/content/mavibot/user-guide/6-btree-configuration.html Sat Dec 21 09:26:40 2013
@@ -17,7 +17,7 @@
-->
<html>
<head>
- <title>6 - BTree configuration — Apache Directory</title>
+ <title>6 - Mavibot B-tree configuration — Apache Directory</title>
<link href="./../../css/common.css" rel="stylesheet" type="text/css">
<link href="./../../css/turquoise.css" rel="stylesheet" type="text/css">
@@ -134,7 +134,7 @@
<div class="nav">
<div class="nav_prev">
- <a href="5-btree-informations.html">5 - BTree information</a>
+ <a href="5-btree-informations.html">5 - Mavibot B-tree information</a>
</div>
<div class="nav_up">
@@ -144,21 +144,21 @@
</div>
<div class="nav_next">
- <a href="7-btree-internals.html">7 - BTree internals</a>
+ <a href="7-btree-internals.html">7 - BMavibot internals</a>
</div>
<div class="clearfix"></div>
</div>
-<h1 id="6-btree-configuration">6 - BTree configuration</h1>
+<h1 id="6-mavibot-b-tree-configuration">6 - Mavibot B-tree configuration</h1>
<p>TODO</p>
<div class="nav">
<div class="nav_prev">
- <a href="5-btree-informations.html">5 - BTree information</a>
+ <a href="5-btree-informations.html">5 - Mavibot B-tree information</a>
</div>
<div class="nav_up">
@@ -168,7 +168,7 @@
</div>
<div class="nav_next">
- <a href="7-btree-internals.html">7 - BTree internals</a>
+ <a href="7-btree-internals.html">7 - BMavibot internals</a>
</div>
<div class="clearfix"></div>