directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1552893 - in /directory/site/trunk/content/mavibot/user-guide: 1.1-btree-basics.mdtext 2-btree-types.mdtext 3-btree-management.mdtext 4-btree-operations.mdtext 5-btree-informations.mdtext 6-btree-configuration.mdtext
Date Sat, 21 Dec 2013 09:26:32 GMT
Author: elecharny
Date: Sat Dec 21 09:26:32 2013
New Revision: 1552893

URL: http://svn.apache.org/r1552893
Log:
Added some content

Modified:
    directory/site/trunk/content/mavibot/user-guide/1.1-btree-basics.mdtext
    directory/site/trunk/content/mavibot/user-guide/2-btree-types.mdtext
    directory/site/trunk/content/mavibot/user-guide/3-btree-management.mdtext
    directory/site/trunk/content/mavibot/user-guide/4-btree-operations.mdtext
    directory/site/trunk/content/mavibot/user-guide/5-btree-informations.mdtext
    directory/site/trunk/content/mavibot/user-guide/6-btree-configuration.mdtext

Modified: directory/site/trunk/content/mavibot/user-guide/1.1-btree-basics.mdtext
URL: http://svn.apache.org/viewvc/directory/site/trunk/content/mavibot/user-guide/1.1-btree-basics.mdtext?rev=1552893&r1=1552892&r2=1552893&view=diff
==============================================================================
--- directory/site/trunk/content/mavibot/user-guide/1.1-btree-basics.mdtext (original)
+++ directory/site/trunk/content/mavibot/user-guide/1.1-btree-basics.mdtext Sat Dec 21 09:26:32
2013
@@ -1,8 +1,8 @@
-Title: 1.1 - BTree Basics
+Title: 1.1 - B-tree Basics
 NavUp: 1-introduction.html
 NavUpText: 1 - Introduction
 NavNext: 2-btree-types.html
-NavNextText: 2 - BTree Types
+NavNextText: 2 - B-tree Types
 Notice: Licensed to the Apache Software Foundation (ASF) under one
     or more contributor license agreements.  See the NOTICE file
     distributed with this work for additional information
@@ -20,5 +20,23 @@ Notice: Licensed to the Apache Software 
     specific language governing permissions and limitations
     under the License.
 
-# 1.1 - BTree Basics
+# 1.1 - B-tree Basics
+
+A **B-tree** "tree data structure that keeps data sorted and allows searches, sequential
access, insertions, and deletions in logarithmic time." (see [Wikipedia](http://en.wikipedia.org/wiki/B-tree))
+
+The important point here is the last one : it guarantees **O(logn)** operations, compared
to any other data structures (a hashed data structure offers **O(n)** average operations,
but can degenerate to **O(n2)**, and ordering is not kept. 
+
+**B-trees** are everywhere : databases, OS, etc. It's a critical data structure when you
are to deal with a huge number of data.
+
+1.1.1 - Inside a B-tree
+
+A **B-Tree** contains **Nodes** and **Leaves**. A *Node* points to other **Nodes** or **Leaves**.
**Leaves** contains **Values**. Both **Nodes** and **Leaves** have **Keys** that are associated
with *Values*.
+
+Pretty simple !
+
+One last thing : **Keys** are ordered, and this is the condition for the easy and fast retrieval
of **Values**.
+
+A few more rules are enforced :
+* A **Node** and a **Leaf** contains up to N values (N being generally a power of 2, so 2,
4, 8, 16...).
+* You can't have less than N/2 **Values** or **keys** in a **Leaf** or a **Node**, except
for the root **Node**.
 

Modified: directory/site/trunk/content/mavibot/user-guide/2-btree-types.mdtext
URL: http://svn.apache.org/viewvc/directory/site/trunk/content/mavibot/user-guide/2-btree-types.mdtext?rev=1552893&r1=1552892&r2=1552893&view=diff
==============================================================================
--- directory/site/trunk/content/mavibot/user-guide/2-btree-types.mdtext (original)
+++ directory/site/trunk/content/mavibot/user-guide/2-btree-types.mdtext Sat Dec 21 09:26:32
2013
@@ -1,10 +1,10 @@
-Title: 2 - BTree Types
+Title: 2 - B-tree Flavors
 NavUp: ../user-guide.html
 NavUpText: User Guide
 NavNext: 3-btree-management.html
-NavNextText: 3 - BTree management
+NavNextText: 3 - Mavibot B-tree management
 NavPrev: 1.1-btree-basics.html
-NavPrevText: 1.1 - BTree Basics
+NavPrevText: 1.1 - B-tree Basics
 Notice: Licensed to the Apache Software Foundation (ASF) under one
     or more contributor license agreements.  See the NOTICE file
     distributed with this work for additional information
@@ -22,6 +22,10 @@ Notice: Licensed to the Apache Software 
     specific language governing permissions and limitations
     under the License.
 
-# 2 - BTree Types
+# 2 - B-tree flavors
 
-TODO
\ No newline at end of file
+You have many different flavors of **B-trees** :
+
+* B+tree : we have a pointer to the next **Node** in each **Node**
+* B*-tree : the internal **Nodes** are compacted, to contain at least 2/3 of the number of
possible slots
+* Counted B*-tree : the **B-tree**
\ No newline at end of file

Modified: directory/site/trunk/content/mavibot/user-guide/3-btree-management.mdtext
URL: http://svn.apache.org/viewvc/directory/site/trunk/content/mavibot/user-guide/3-btree-management.mdtext?rev=1552893&r1=1552892&r2=1552893&view=diff
==============================================================================
--- directory/site/trunk/content/mavibot/user-guide/3-btree-management.mdtext (original)
+++ directory/site/trunk/content/mavibot/user-guide/3-btree-management.mdtext Sat Dec 21 09:26:32
2013
@@ -1,10 +1,10 @@
-Title: 3 - BTree management
+Title: 3 - Mavibot B-tree management
 NavUp: ../user-guide.html
 NavUpText: User Guide
 NavNext: 4-btree-operations.html
-NavNextText: 4 - BTree operations
+NavNextText: 4 - Mavibot B-tree operations
 NavPrev: 2-btree-types.html
-NavPrevText: 2 - BTree types
+NavPrevText: 2 - Mavibot B-tree types
 Notice: Licensed to the Apache Software Foundation (ASF) under one
     or more contributor license agreements.  See the NOTICE file
     distributed with this work for additional information
@@ -22,6 +22,6 @@ Notice: Licensed to the Apache Software 
     specific language governing permissions and limitations
     under the License.
 
-# 3 - BTree management
+# 3 - Mavibot B-tree management
 
 TODO
\ No newline at end of file

Modified: directory/site/trunk/content/mavibot/user-guide/4-btree-operations.mdtext
URL: http://svn.apache.org/viewvc/directory/site/trunk/content/mavibot/user-guide/4-btree-operations.mdtext?rev=1552893&r1=1552892&r2=1552893&view=diff
==============================================================================
--- directory/site/trunk/content/mavibot/user-guide/4-btree-operations.mdtext (original)
+++ directory/site/trunk/content/mavibot/user-guide/4-btree-operations.mdtext Sat Dec 21 09:26:32
2013
@@ -1,10 +1,10 @@
-Title: 4 - BTree operations
+Title: 4 - Mavibot B-tree operations
 NavUp: ../user-guide.html
 NavUpText: User Guide
 NavNext: 5-btree-informations.html
-NavNextText: 5 - BTree information
+NavNextText: 5 - Mavibot B-tree information
 NavPrev: 3-btree-management.html
-NavPrevText: 3 - BTree management
+NavPrevText: 3 - Mavibot B-tree management
 Notice: Licensed to the Apache Software Foundation (ASF) under one
     or more contributor license agreements.  See the NOTICE file
     distributed with this work for additional information
@@ -22,21 +22,21 @@ Notice: Licensed to the Apache Software 
     specific language governing permissions and limitations
     under the License.
 
-# 4 - BTree operations
+# 4 - Mavibot B-tree operations
 
-We will now list all the possible operations that can be applied on a **BTree**. But first,
let us understand the _Cursor_ interface, as it is used for navigating a **BTree** using various
types of _browse_ operations.
+We will now list all the possible operations that can be applied on a **B-tree**. But first,
let us understand the _Cursor_ interface, as it is used for navigating a **B-tree** using
various types of _browse_ operations.
 
 ## 4.1 The Cursor interface
 
-All the _browse_ operations will return a _Cursor_ instance. A _Cursor_ allows navigating
forward and backward on a **BTree**. It starts at a specific position, and can be moved to
a specific position too. The default position for a _Cursor_ is before the very first element
of the **BTree**
+All the _browse_ operations will return a _Cursor_ instance. A _Cursor_ allows navigating
forward and backward on a **B-tree**. It starts at a specific position, and can be moved to
a specific position too. The default position for a _Cursor_ is before the very first element
of the **B-tree**
 
 <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>
 
-Here is the **BTree** sample we will use for the following examples :
+Here is the **B-tree** sample we will use for the following examples :
 
-![Sample BTree](images/ug-btree-sample.png)
+![Sample B-tree](images/ug-btree-sample.png)
 
 
 ### 4.1.1 Cursor position management
@@ -105,5 +105,5 @@ Now that we know what a _Cursor_ is abou
 
 ### 4.1.1 browse()
 
-This method returns a cursor with the position set before the first key of the **BTree**.

+This method returns a cursor with the position set before the first key of the **B-tree**.

 

Modified: directory/site/trunk/content/mavibot/user-guide/5-btree-informations.mdtext
URL: http://svn.apache.org/viewvc/directory/site/trunk/content/mavibot/user-guide/5-btree-informations.mdtext?rev=1552893&r1=1552892&r2=1552893&view=diff
==============================================================================
--- directory/site/trunk/content/mavibot/user-guide/5-btree-informations.mdtext (original)
+++ directory/site/trunk/content/mavibot/user-guide/5-btree-informations.mdtext Sat Dec 21
09:26:32 2013
@@ -1,10 +1,10 @@
-Title: 5 - BTree information
+Title: 5 - Mavibot B-tree information
 NavUp: ../user-guide.html
 NavUpText: User Guide
 NavNext: 6-btree-configuration.html
-NavNextText: 6 - BTree configuration
+NavNextText: 6 - Mavibot B-tree configuration
 NavPrev: 4-btree-operations.html
-NavPrevText: 4 - BTree operations
+NavPrevText: 4 - Mavibot B-tree operations
 Notice: Licensed to the Apache Software Foundation (ASF) under one
     or more contributor license agreements.  See the NOTICE file
     distributed with this work for additional information
@@ -22,6 +22,6 @@ Notice: Licensed to the Apache Software 
     specific language governing permissions and limitations
     under the License.
 
-# 5 - BTree information
+# 5 - Mavibot B-tree information
 
 TODO
\ No newline at end of file

Modified: directory/site/trunk/content/mavibot/user-guide/6-btree-configuration.mdtext
URL: http://svn.apache.org/viewvc/directory/site/trunk/content/mavibot/user-guide/6-btree-configuration.mdtext?rev=1552893&r1=1552892&r2=1552893&view=diff
==============================================================================
--- directory/site/trunk/content/mavibot/user-guide/6-btree-configuration.mdtext (original)
+++ directory/site/trunk/content/mavibot/user-guide/6-btree-configuration.mdtext Sat Dec 21
09:26:32 2013
@@ -1,10 +1,10 @@
-Title: 6 - BTree configuration
+Title: 6 - Mavibot B-tree configuration
 NavUp: ../user-guide.html
 NavUpText: User Guide
 NavNext: 7-btree-internals.html
-NavNextText: 7 - BTree internals
+NavNextText: 7 - BMavibot internals
 NavPrev: 5-btree-informations.html
-NavPrevText: 5 - BTree information
+NavPrevText: 5 - Mavibot B-tree information
 Notice: Licensed to the Apache Software Foundation (ASF) under one
     or more contributor license agreements.  See the NOTICE file
     distributed with this work for additional information
@@ -22,6 +22,6 @@ Notice: Licensed to the Apache Software 
     specific language governing permissions and limitations
     under the License.
 
-# 6 - BTree configuration
+# 6 - Mavibot B-tree configuration
 
 TODO
\ No newline at end of file



Mime
View raw message