org.deegree.io.dbaseapi
Class DBaseIndex

java.lang.Object
  org.deegree.io.dbaseapi.DBaseIndex

public class DBaseIndex
extends Object

A class for reading from and writing to DBase index files (*.ndx), maybe not 100% xbase compatible!

The fileformat is described at http://www.e-bachmann.dk/computing/databases/xbase/index.html

This index is suitable for indexing both unique and non-unique columns. Unique indexing is much faster than non-unique because it use a faster algorithm.

The index file is a B+tree (sometimes called a paged B-tree) that consist of pages. There are two page types, leaves and non-leafs. The starting page (eg. the page the search algorithm starts) is the root page.

Searching goes as follows:

• load the root page (eg. the starting page)
• if the page is a leaf
  • search for the requested key
• if the page is not a leaf (eg. the page has subpages)
  • search for a key that is equal to or bigger than the requested key
  • load the lower page
  • continue searching inside the lower page

Above algorithm is implemented in two different methods, one for unique indexes and one for non-unique indexes. Searching unique indexes is easier because the algorithm is finished as soon as it has found a key, the non-unique version of the algorithm has to find all keys present in the index.

Inserting goes as follows:

• find the leaf page the key has to insert in
• insert the key in the leaf page
• if the leaf page is full (eg. validEntries > noOfKeysPerPage)
  • split the leaf page (results in two leaf pages)
  • add the first item of the new page to the parent page
• if the parent page is also full
  • split the parent page
  • add the first item of the new page to it's parent page
  • etc.

If a page that splits does not have a parent page then a new page is created. This page is the new starting page

Handling different data types: The index can handle strings and numbers. Numbers are always stored als IEEE doubles. The method addKey checks the given key and throws an exception if the datatype of the key doesn't suit the index

Author:

Reijer Copier, email: reijer.copier@idgis.nl

Nested Class Summary

class

DBaseIndex.Cache Inner class for the cache.

Field Summary

protected byte[]	b
protected int	cacheSize
protected RandomAccessFile	file
protected byte[]	keyBytes
protected int	keyLength
protected int	keyType
protected int	noOfKeysPerPage
protected int	numberOfPages
protected byte[]	page
protected int	sizeOfKeyRecord
protected int	startingPageNo

Constructor Summary

DBaseIndex(String name)
Open an existing .ndx file

Method Summary

void	addKey(Comparable key, int record) Add a key to the index
void	close() Close the index file
static DBaseIndex	createIndex(String name, String column, int keyLength, boolean uniqueFlag, boolean numbers) Create a new index
void	flush() Flush all the buffers
int	getDepth() Calculate the depth for the index
protected org.deegree.io.dbaseapi.DBaseIndex.Page	getPage(int number) Get a page
boolean	isUnique() Contains this index unique values?
protected org.deegree.io.dbaseapi.DBaseIndex.Page	newPage() Create a new page
int[]	search(Comparable key)
protected void	setRoot(org.deegree.io.dbaseapi.DBaseIndex.Page page) Set the root page
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

file

protected RandomAccessFile file

startingPageNo

protected int startingPageNo

numberOfPages

protected int numberOfPages

sizeOfKeyRecord

protected int sizeOfKeyRecord

keyLength

protected int keyLength

noOfKeysPerPage

protected int noOfKeysPerPage

keyType

protected int keyType

b

protected byte[] b

page

protected byte[] page

keyBytes

protected byte[] keyBytes

cacheSize

protected int cacheSize

Constructor Detail

DBaseIndex

public DBaseIndex(String name)
           throws IOException

Open an existing .ndx file

Throws:

IOException

Method Detail

getPage

protected org.deegree.io.dbaseapi.DBaseIndex.Page getPage(int number)
                                                   throws IOException

Get a page

Throws:

IOException

newPage

protected org.deegree.io.dbaseapi.DBaseIndex.Page newPage()
                                                   throws IOException

Create a new page

Throws:

IOException

setRoot

protected void setRoot(org.deegree.io.dbaseapi.DBaseIndex.Page page)

Set the root page

createIndex

public static DBaseIndex createIndex(String name,
                                     String column,
                                     int keyLength,
                                     boolean uniqueFlag,
                                     boolean numbers)
                              throws IOException

Create a new index

Throws:

IOException

flush

public void flush()
           throws IOException

Flush all the buffers

Throws:

IOException

close

public void close()
           throws IOException

Close the index file

Throws:

IOException

search

public int[] search(Comparable key)
             throws IOException,
                    KeyNotFoundException,
                    InvalidKeyTypeException

Throws:

IOException

KeyNotFoundException

InvalidKeyTypeException

addKey

public void addKey(Comparable key,
                   int record)
            throws IOException,
                   KeyAlreadyExistException,
                   InvalidKeyTypeException,
                   KeyTooLongException

Add a key to the index

Throws:

IOException

KeyAlreadyExistException

InvalidKeyTypeException

KeyTooLongException

getDepth

public int getDepth()
             throws IOException

Calculate the depth for the index

Throws:

IOException

isUnique

public boolean isUnique()

Contains this index unique values?

toString

public String toString()

Overrides:

toString in class Object