directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From conflue...@apache.org
Subject [CONF] Apache Directory Server v1.5 > Table and Cursor Implementations
Date Thu, 16 Jun 2011 13:31:00 GMT
<html>
<head>
    <base href="https://cwiki.apache.org/confluence">
            <link rel="stylesheet" href="/confluence/s/2042/9/1/_/styles/combined.css?spaceKey=DIRxSRVx11&amp;forWysiwyg=true"
type="text/css">
    </head>
<body style="background: white;" bgcolor="white" class="email-body">
<div id="pageContent">
<div id="notificationFormat">
<div class="wiki-content">
<div class="email">
    <h2><a href="https://cwiki.apache.org/confluence/display/DIRxSRVx11/Table+and+Cursor+Implementations">Table
and Cursor Implementations</a></h2>
    <h4>Page <b>edited</b> by             <a href="https://cwiki.apache.org/confluence/display/~elecharny">Emmanuel
L├ęcharny</a>
    </h4>
        <br/>
                         <h4>Changes (1)</h4>
                                 
    
<div id="page-diffs">
                    <table class="diff" cellpadding="0" cellspacing="0">
    
            <tr><td class="diff-snipped" >...<br></td></tr>
            <tr><td class="diff-unchanged" >JdbmTable has several helper classes
which include a few Cursor implementations.  These Cursors abstract the JDBM specific browsing
mechanism while also adding support for traversal over duplicate keys if they have been enabled
in the Table.  There are six main Cursor implementations. <br> <br></td></tr>
            <tr><td class="diff-added-lines" style="background-color: #dfd;">h2.
Introduction to Cursors <br> <br>A *Cursor* is a data structure that allows to
access inner data eiher forward or backward. The following schema expose the different kind
of operations on elements that can be applied to a cursor. <br> <br>!cursor.png|border=1!
<br> <br>We also have some other operations that give a status : <br>* isFirst()
<br>* isBeforeFirst() <br>* isLast() <br>* isAfterLast() <br>* isClosed()
<br>* available() <br> <br>and a few more operations : <br>* before(
Element ) <br>* after( Element ) <br>* close() and close( Exception ) <br>*
setClosureMonitor() <br> <br> <br></td></tr>
            <tr><td class="diff-unchanged" >h2. No Duplicates Cursor <br>
<br></td></tr>
            <tr><td class="diff-snipped" >...<br></td></tr>
    
            </table>
    </div>                            <h4>Full Content</h4>
                    <div class="notificationGreySide">
        <h1><a name="TableandCursorImplementations-TableInterfaceObjectives"></a>Table
Interface Objectives</h1>

<p>A Table is the most atomic element in a (disk or memory) based partition backed by
data structures acting as 2 column lookup tables where the keys are sorted and can be browsed.
Underlying data structures may be disk or memory based.  They may support <b>duplicate
keys</b> where more than one value for a key can be stored.  With duplicate keys values
are also sorted. </p>

<p>The primary objective of the Table interface is to abstract away and adapt data structures
to provide a standard syntactic and semantic representation which is used by higher layers.
 This abstraction enables the reuse of different data structures in implementations while
utilizing the same table/index structure to store and search entries.</p>

<h1><a name="TableandCursorImplementations-JDBMCharacteristics"></a>JDBM
Characteristics</h1>

<p>JDBM is primarily a disk based B+Tree implementation.  JDBM, unlike for example JE,
is limited by the fact that it cannot store more than one value for a key.  Hence JDBM does
not support duplicate keys.</p>

<p>JDBM uses a record manager to manage BTrees in a file.  Many BTrees may reside within
a JDBM db file.  JDBM caches blocks of records in these files (these are not deserialized
representations of entries) as raw bytes.  Keys and values are represented internally as byte
arrays. </p>

<p>JDBM sorts keys and utilizes Comparators to compare them while inserting keys into
the B+Tree. It also provides a Serializer interface which can be used to [de]serialize keys
and values to use in place of default Java Serialization.</p>

<p>JDBM allows table entry browsing using a simple Browser interface which returns key
value tuples.  Both forward and reverse browsing is possible with browser positioning at the
front, end, and on specific keys.  Note that the Tuple objects returned by the browser are
reused (a new Tuple object is not created for each step forward or reverse).</p>

<h1><a name="TableandCursorImplementations-JDBMTableImplementation"></a>JDBM
Table Implementation</h1>

<p>The JdbmTable class implements the Table interface.  This implementation abstracts
JDBM specific B+Tree implementation details.  The majority of the code in this class and it's
helpers deals with adding duplicate key support to JDBM B+Trees.</p>

<p>A Table can be created with or without support for duplicate keys.  When the JdbmTable
is created it is designated as either supporting or not supporting duplicates.  The constructor
used determines if support for duplicate keys are enabled or disabled.</p>

<p>Since JDBM natively does not support duplicates we mimic support for duplicate keys
using two value storage techniques described below.  </p>

<h2><a name="TableandCursorImplementations-ValueStorageTechnique%3ABulkValueSerialization"></a>Value
Storage Technique: Bulk Value Serialization</h2>

<p>This first technique uses an in memory BTree implementation to store the values of
the key.  Eventually we want the in memory B+Tree implementation to be pluggable.  Presently
a linked (a.k.a. threaded) AVL tree optimized for bulk serialization and traversal is used.</p>

<p>The set of values for a key in this in-memory data structure are serialized and stored
into the value of the JDBM B+Tree tuple.  When the key is looked up, the data structure is
deserialized.  Custom serialization is used here to override default Java Serialization thereby
avoid performance issues.  Note that the in-memory data structure storing the set of values
delegates value object serialization to a value Serializer set on the Table.  This technique
works well up to a point where the number of values for a key are small.  After some threshold
the cost of bulk serialization outweighs the disk access costs of the second mechanism below.</p>

<h2><a name="TableandCursorImplementations-ValueStorageTechnique%3ABTreeRedirection"></a>Value
Storage Technique: BTree Redirection</h2>

<p>The second mechanism uses another JDBM B+Tree in the same file to store the values
of duplicate keys. In this secondary BTree all tuple values are empty.  Only the key field
of the secondary BTree is used and it stores the values of the key in the primary table.</p>

<p>The entry in the primary BTree uses a reference in it's value field.  So when the
key is looked up in the primary table, a serialized representation of a BTreeRedirect object
is found in the value field.  This redirect object contains the record identifier for the
secondary BTree within the same file, managed by the same JDBM record manager.</p>

<p>Just like the in memory representation of multiple values for a key, this JDBM BTree
can be browsed. </p>

<p>The JdbmTable uses a threshold parameter to switch between these two mechanisms on
a per key basis.  Meaning both mechanisms may be in use each for a different key.  The JdbmTable
detects the mechanism used using a magic number embedded in the value at the first byte. This
magic number let's the implementation know if the value represents an AvlTree or BTreeRedirect
object.  Based on the value different marshaling algorithms are used.</p>

<h1><a name="TableandCursorImplementations-CursorImplementations"></a>Cursor
Implementations</h1>

<p>JdbmTable has several helper classes which include a few Cursor implementations.
 These Cursors abstract the JDBM specific browsing mechanism while also adding support for
traversal over duplicate keys if they have been enabled in the Table.  There are six main
Cursor implementations.</p>

<h2><a name="TableandCursorImplementations-IntroductiontoCursors"></a>Introduction
to Cursors</h2>

<p>A <b>Cursor</b> is a data structure that allows to access inner data
eiher forward or backward. The following schema expose the different kind of operations on
elements that can be applied to a cursor.</p>

<p><span class="image-wrap" style=""><img src="/confluence/download/attachments/79736/cursor.png?version=1&amp;modificationDate=1308230780912"
style="border: 1px solid black" /></span></p>

<p>We also have some other operations that give a status :</p>
<ul>
	<li>isFirst()</li>
	<li>isBeforeFirst()</li>
	<li>isLast()</li>
	<li>isAfterLast()</li>
	<li>isClosed()</li>
	<li>available()</li>
</ul>


<p>and a few more operations :</p>
<ul>
	<li>before( Element )</li>
	<li>after( Element )</li>
	<li>close() and close( Exception )</li>
	<li>setClosureMonitor()</li>
</ul>



<h2><a name="TableandCursorImplementations-NoDuplicatesCursor"></a>No Duplicates
Cursor</h2>

<p>The no duplicates Cursor is intended for use only with JdbmTables that have duplicate
keys disabled.  This Cursor browses Table Tuples containing the key and the value.  If duplicates
are not enabled, calls to cursor() with no arguments return this Cursor implementation.</p>

<h2><a name="TableandCursorImplementations-DuplicateContainerCursor"></a>Duplicate
Container Cursor</h2>

<p>The duplicate container cursor is very similar to a no duplicates Cursor however
it is only used by JdbmTables that have duplicate keys enabled.  Instead of returning Tuples
with key value pairs, it returns a Tuple with a key and container for the values of that key.
 This container is a wrapper around either a BTree redirect object or a AVL tree.  This Cursor
is used internally as an underlying Cursor by the duplicates Cursor which is described below.
 It is never directly returned to callers when a Cursor is requested.  </p>

<h2><a name="TableandCursorImplementations-DuplicatesCursor"></a>Duplicates
Cursor</h2>

<p>The duplicates Cursor is only used by JdbmTables that have duplicate keys enabled.
 When duplicate keys are enabled calls to cursor() with no arguments returns this kind of
Cursor.  </p>

<p>The duplicates Cursor returns Tuple objects on browsing operations with a key and
a value object respectively as designated by the generic types used by the Table.  This Cursor
will transparently browse keys with and without multiple values returning Tuples with the
same key, iff that key contains multiple values. Once all the values of a key are traversed
it moves on to the next key.  For example consider the sample table composition below:</p>

<div class="preformatted panel" style="border-width: 1px;"><div class="preformattedContent
panelContent">
<pre>(-3, 10)
(52, 25)
(52, 38)
(52, 40)
(97, 58)
</pre>
</div></div>

<p>When positioned before the first element, the call to next() will position this Cursor
over the Tuple (-3, 100).  Another next() call will position it over (52, 25) and yet another
will position it over (52, 38) and so on with (52, 40), and finally (97, 58).  This Cursor
makes it seem as though duplicate key support is provided by the browsing capabilities of
the JdbmTable.</p>

<h2><a name="TableandCursorImplementations-SameKeyBTreeValueCursor"></a>Same-Key
BTree <b>Value</b> Cursor</h2>

<p>The same-key BTree value Cursor is intend for browsing only the value or values of
a specific key.  It returns only value objects instead of returning Tuples on browsing operations.
 This is because the key is already known and does not change.</p>

<p>This Cursor is not critical but rather facilitates an optimization.  Users wanting
to browse the values of a key need not have to resort to a duplicates Cursor which does not
start and stop on a specific key automatically.  If a duplicates Cursor is used each browsing
operation much check to see if the Cursor is still on the same intended key.  This overhead
along with key value copies into a Tuple can be avoided when using this Cursor.</p>

<h2><a name="TableandCursorImplementations-SameKeyBTreeTupleCursor"></a>Same-Key
BTree <b>Tuple</b> Cursor</h2>

<p>This cursor like the same-key BTree value cursor above is bound to traverse only
Tuples of the same key. The difference however is that this Cursor returns a key/value Tuple
object with the same key and instead of just returning the value object.</p>

<h2><a name="TableandCursorImplementations-AvlTreeTupleCursor"></a>AvlTree
Tuple Cursor</h2>

<p>This is similar to the same-key BTree Tuple Cursor above except it traverses an in
memory AvlTree which only contains the values of the same key anyway.  Instead of returning
values this Cursor returns key/value Tuples for each value in the AvlTree as it traverses
it using the same key across all values traversed.</p>


    </div>
        <div id="commentsSection" class="wiki-content pageSection">
        <div style="float: right;">
            <a href="https://cwiki.apache.org/confluence/users/viewnotifications.action"
class="grey">Change Notification Preferences</a>
        </div>
        <a href="https://cwiki.apache.org/confluence/display/DIRxSRVx11/Table+and+Cursor+Implementations">View
Online</a>
        |
        <a href="https://cwiki.apache.org/confluence/pages/diffpagesbyversion.action?pageId=79736&revisedVersion=8&originalVersion=7">View
Changes</a>
            </div>
</div>
</div>
</div>
</div>
</body>
</html>

Mime
View raw message