perst.html

Perst开源实时数据库

<LI>key is greater or equals to MIN_VAL
<LI>key is less than than MAX_VAL
<LI>key is less than or equals to MAX_VAL
</OL><P>

There are several different ways of selecting objects using index:
<DL>
<DT><code>IPersistent get(Key key)</code>
<DD>Get object by key. This method should be used for unique indices to locate object by exact key value.
<DT><code>IPersistent[] get(Key from, Key till)</code>
<DD>Get array of objects with key belonging to the specified range. Either from boundary, either till boundary either both of them can be <code>null</code>. Both boundaries can be inclusive or exclusive.
<DT><code>IEnumerator GetEnumerator()</code>
<DD>Get iterator which will traverse all objects in the index in key ascending order.
You can use index in <code>foreach</code> construction to iterate through all indexed objects. 
<DT><code>IEnumerator GetEnumerator(Key from, Key till, IterationOrder order)</code>
<DD>Get iterator for objects with key belonging to the specified range. Either from boundary, either till boundary either both of them can be <code>null</code>. Both boundaries can be inclusive or exclusive. Objects can be traversed in key ascending or descending order .
</DL><P>

If you need set of persistent objects you should use <code>Storage.createSet</code> method.
Set is implemented using B+Tree where object OID is used as a key.<P> 

PERST also support spatial indices (<code>org.garret.perst.SpatialIndex</code>) and generic indices with
user defined comparator (<code>org.garret.perst.SortedCollection</code>). 
Spatial index is implemented using Guttman's R-Tree with quadratic split algorithm.
It allows efficient search of R2 objects. Sorted collection provides almost the same methods
as <code>FieldIndex</code> but it uses user defined comparator to compare collection members.
Sorted collection is implemented using T-Tree and is especially efficient for main-memory
databases.</P>

The table below summarize information about all indeices supported by PERST:

<TABLE border>
<TR><TH>Interface</TH><TH>Description</TH><TH>Key type</TH><TH>Implementation</TH><TH>Created by</TH></TH>
<TR>
<TD><code>Index</code></TD>
<TD>Index with explicitely specified key used for exact match or range queries</TD>
<TD>scalar, string or reference</TD>
<TD align=center>B+Tree</TD>
<TD><code>Storage.CreateIndex(Type type, boolean unique)</code></TD>
</TR>
<TR>
<TD><code>Index</code></TD>
<TD>The same as above but assuming that there can be a lot of duplicate key values</TD>
<TD>scalar, string or reference</TD>
<TD align=center>B+Tree</TD>
<TD><code>Storage.CreateThinkIndex(Type type)</code></TD>
</TR>
<TR>
<TD><code>Index</code></TD>
<TD>Random access index optimized for accessing elements both by key and by position
<TD>scalar, string or reference</TD>
<TD align=center>B+Tree</TD>
<TD><code>Storage.CreateRandomAccessIndex(Type type, bool unique)</code></TD>
</TR>
<TR>
<TD><code>FieldIndex</code></TD>
<TD>Index constructed for one of the object fields</TD>
<TD>scalar, string or reference</TD>
<TD align=center>B+Tree</TD>
<TD><code>Storage.CreateFieldIndex(Type type, String fieldName, boolean unique)</code></TD>
</TR>
<TR>
<TD><code>FieldIndex</code></TD>
<TD>Random access field index optimized for accessing elements both by key and by position</TD>
<TD>scalar, string or reference</TD>
<TD align=center>B+Tree</TD>
<TD><code>Storage.createRandomAccessFieldIndex(Type type, string fieldName, bool unique)</code></TD>
</TR>
<TR>
<TD><code>BitIndex</code></TD>
<TD>Bit index for searching object by bitmap of properties</TD>
<TD>persistent object</TD>
<TD align=center>B+Tree</TD>
<TD><code>Storage.CreateBitIndex()</code></TD>
</TR>
<TR>
<TD><code>ISet</code></TD>
<TD>Set of persistent objects</TD>
<TD>-</TD>
<TD align=center>B+Tree</TD>
<TD><code>Storage.CreateSet()</code></TD>
</TR>
<TR>
<TD><code>IPersistentSet</code></TD>
<TD>Scalable set of persistent objects (can efficienty handle both small and large number of members)</TD>
<TD>persistent object</TD>
<TD align=center>Link or B+Tree</TD>
<TD><code>Storage.CreateScalableSet()</code></TD>
</TR>
<TR>
<TD><code>IPersistentList</code></TD>
<TD>List of persistent objects providing random access</TD>
<TD>persistent object</TD>
<TD align=center>B+Tree</TD>
<TD><code>Storage.CreateList()</code></TD>
</TR>
<TR>
<TD><code>IPersistentList</code></TD>
<TD>Scalable list of persistent objects (can efficienty handle both small and large number of members)</TD>
<TD>persistent object</TD>
<TD align=center>Link or B+Tree</TD>
<TD><code>Storage.CreateScalableList()</code></TD>
</TR>
<TD><code>IPersistentMap</code></TD>
<TD>Map of of persistent objects (can efficienty handle both small and large number of members)</TD>
<TD>persistent object</TD>
<TD align=center>Sorted array or B+Tree</TD>
<TD><code>Storage.CreateMap(Type keyType)</code></TD>
</TR>
<TR>
<TR>
<TD><code>SpatialIndex</code></TD>
<TD>Index for spatial objects</TD>
<TD>Rectangle</TD>
<TD align=center>R-Tree</TD>
<TD><code>Storage.CreateSpatialIndex()</code></TD>
</TR>
<TR>
<TD><code>SpatialIndexR2</code></TD>
<TD>Index for spatial objects with real coordinates</TD>
<TD>RectangleR2</TD>
<TD align=center>R-Tree</TD>
<TD><code>Storage.CreateSpatialIndexR2()</code></TD>
</TR>
<TR>
<TD><code>SortedCollection</code></TD>
<TD>Index with user defined comparator</TD>
<TD>any</TD>
<TD align=center>T-Tree</TD>
<TD><code>Storage.CreateSortedCollection(PersistentComparator comparator, boolean unique)</code></TD>
</TR>
</TABLE><P>


<H3> <A NAME = "projection">Projection</A></H3>

Using PERST indices programmer can easily implement most of simple SQL queries, like:

<pre>
    select * from T where x=?;
</pre>

PERST relations can be used to implement simple joins, 
like the following SQL query fetching all order to the particular vendor:

<pre>
    select * from O Order, V Vendor where O.vendorID = V.id AND V.name='ABC';
</pre>

In PERST it is possible to select first vendor using index search and ten traverse 
correspondent relation to locate all orders to this vendor.<P>

But sometimes it is needed to implement more complex queries.
It is also possible in Perst without need to write query in some special 
(non-procedural) language. Class <code>Projection</code> is use to combine results
of several simple operations (such index search). Lets start explanation of this class with an 
example. Consider that we need to know all order for the detail with name started with 'D1' 
shipped by vendors with name started with 'V1' or 'V3'. 
SQL statement which perform this query is the following:

<pre>
    select * from O Order, V Vendor, D Detail where D.name like 'D1%' and O.detailID = D.id
        and O.vendorID = V.id and (V.name like 'V1%' OR V.name like 'V3%');
</pre>


And now how it can be done in Perst. Consider that we have indices for 
details and vendors:

<pre>
    FieldIndex detailIndex = db.CreateFieldIndex(typeof(Detail), "name", true);
    FieldIndex vendorIndex = db.CreateFieldIndex(typeof(Vendor), "name", true);
</pre>


Set of requested orders can be obtained in the following way:

<pre>
    //  Projection from vendors to orders (using "orders" field of Link type)
    Projection v2o = new Projection(typeof(Vendor), "orders");
    //  Projection from details to orders (using "orders" field of Link type)
    Projection d2o = new Projection(typeof(Detail), "orders");
    // Select vendors with name like 'V1%'
    v2o.Project(vendorIndex.StartsWith("V1"));
    // Select vendors with name like 'V3%'
    v2o.Project(vendorIndex.StartsWith("V3"));
    // Select details with name like 'D1%'
    d2o.Project(detailIndex.StartsWith("D1"));
    // Join projections
    v2o.Join(d2o);
    // Get array of requested orders
    Order[] orders = (Order[])v2o.ToArray(typeof(Order)]);
</pre>

So, as you see Projection class is used for several purposes:

<OL>
<LI>Combine result of several simple operations (implementing OR operator)
<LI>Eliminate duplicates of such merge
<LI>Get set of related objects (perform projection using specified projection field)
<LI>Join several projections (analogue of SQL JOIN)
</OL><P>

It is possible to derive your own class from <code>Projection</code> to implement 
more sophisticated projections than using single projection field.<P>

If you need to sort selection in some particular order, then most efficient way 
is to use <code>FieldIndex</code> for it. When you select objects using index, selected objects
are sorted by search key. If you need to sort selection by field which is not search key, 
than you can use <code>Array.Sort</code> method. For example if in the query described above
we need to sort orders by price field, it can be done with the following statement:

<pre>
    Array.Sort(orders, Order.PriceComparer);
</pre><P>


<H3> <A NAME = "transaction">Transaction model</A></H3>

PERST preserve consistency of the data in case of system or application failure. 
Transaction mechanism is used to implement all-or-nothing database update. 
Transaction in PERST are started implicitly when update operation is first time performed 
and finished explicitly by <code>commit, rollback</code> or <code>close</code> methods.<P>

Commit of transaction cause synchronous write of changed pages to the disk.
Synchronous write (application is blocked until data is really flushed to the disk) is very expensive operation.
Average positioning time for modern disks is about 10ms, so them are usually not able to perform in one second
more than 100 writes in random places. As far as transaction usually consists of several updated pages, 
it leads to average performance about 10 transaction commits per second.<P>

Performance can be greatly increased if you minimize number of commits (larger transactions).
PERST is using shadow mechanism for transaction implementation. When object is changed first time
during transaction, shadow of the object is created and original object is kept unchanged. If 
object is updated multiple times during transaction, shadow is create only once. 
Because of using shows, PERST do not need transaction log file. So in PERST
long transaction can not cause transaction log overflow as in most of other DBMSes.
Quite the contrary, if you do not call commit at all, PERST works as DBMS without transaction
support, adding almost no overhead of supporting transactions.<P>

The only drawback of long transactions is possibility to loose a lot of changes in case of fault.
PERST will preserve consistency of the database, but all changes made since list commit will be lost.<P> 

<H3> <A NAME = "replication">Replication</A></H3>

Perst supports master-slave replication mechanism. It allows to have single master node and
several slave nodes. All updates of the database can happen only at master node and
are replicated to slave nodes. Slave nodes are able to execute read-only requests
working with shadow snapshot of the database (state after last commit).<p>

Replication is page based - all dirty pages from master node page pool are sent to 
slave nodes. Slave node detects moment of transaction commit (when root page is sent
to the slave node and state index is changed in database header) and set exclusive lock in this case.
Read-only transaction at slave node are setting shared lock and working with previous (consistent)