directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From build...@apache.org
Subject svn commit: r891336 - in /websites/staging/directory/trunk/content: ./ mavibot/user-guide/
Date Sat, 21 Dec 2013 09:26:41 GMT
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 &mdash; Apache Directory</title>
+		<title>1.1 - B-tree Basics &mdash; 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 &mdash; Apache Directory</title>
+		<title>2 - B-tree Flavors &mdash; 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 &mdash; Apache Directory</title>
+		<title>3 - Mavibot B-tree management &mdash; 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 &mdash; Apache Directory</title>
+		<title>4 - Mavibot B-tree operations &mdash; 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 &mdash; Apache Directory</title>
+		<title>5 - Mavibot B-tree information &mdash; 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 &mdash; Apache Directory</title>
+		<title>6 - Mavibot B-tree configuration &mdash; 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>



Mime
View raw message