org.deegree_impl.io.shpapi
Class DBaseIndex

java.lang.Object
  org.deegree_impl.io.shpapi.DBaseIndex

public class DBaseIndex

extends java.lang.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.
private class	DBaseIndex.KeyEntry Inner class for the key entries
private class	DBaseIndex.Page Inner class for the pages

Field Summary

protected byte[]	b
private DBaseIndex.Cache	cache
protected int	cacheSize
protected java.io.RandomAccessFile	file
private java.lang.String	fileName
protected byte[]	keyBytes
protected int	keyLength
protected int	keyType
protected int	noOfKeysPerPage
protected int	numberOfPages
protected byte[]	page
protected int	sizeOfKeyRecord
protected int	startingPageNo
private boolean	uniqueFlag

Constructor Summary

	DBaseIndex(java.lang.String name) Open an existing .ndx file
private	DBaseIndex(java.lang.String name, int startingPageNo, int numberOfPages, int sizeOfKeyRecord, int keyLength, int noOfKeysPerPage, int keyType, boolean uniqueFlag, java.io.RandomAccessFile file) Used by createIndex()

Method Summary

void	addKey(java.lang.Comparable key, int record) Add a key to the index
void	close() Close the index file
static DBaseIndex	createIndex(java.lang.String name, java.lang.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 DBaseIndex.Page	getPage(int number) Get a page
boolean	isUnique() Contains this index unique values?
protected DBaseIndex.Page	newPage() Create a new page
int[]	search(java.lang.Comparable key)
protected void	setRoot(DBaseIndex.Page page) Set the root page
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

fileName

private java.lang.String fileName

file

protected java.io.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

uniqueFlag

private boolean uniqueFlag

b

protected byte[] b

page

protected byte[] page

keyBytes

protected byte[] keyBytes

cacheSize

protected int cacheSize

cache

private DBaseIndex.Cache cache

Constructor Detail

DBaseIndex

public DBaseIndex(java.lang.String name)
           throws java.io.IOException

Open an existing .ndx file

DBaseIndex

private DBaseIndex(java.lang.String name,
                   int startingPageNo,
                   int numberOfPages,
                   int sizeOfKeyRecord,
                   int keyLength,
                   int noOfKeysPerPage,
                   int keyType,
                   boolean uniqueFlag,
                   java.io.RandomAccessFile file)

Used by createIndex()

Method Detail

getPage

protected DBaseIndex.Page getPage(int number)
                           throws java.io.IOException

Get a page

Throws:

java.io.IOException

newPage

protected DBaseIndex.Page newPage()
                           throws java.io.IOException

Create a new page

Throws:

java.io.IOException

setRoot

protected void setRoot(DBaseIndex.Page page)
                throws java.io.IOException

Set the root page

Throws:

java.io.IOException

createIndex

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

Create a new index

Throws:

java.io.IOException

flush

public void flush()
           throws java.io.IOException

Flush all the buffers

Throws:

java.io.IOException

close

public void close()
           throws java.io.IOException

Close the index file

Throws:

java.io.IOException

search

public int[] search(java.lang.Comparable key)
             throws java.io.IOException,
                    KeyNotFoundException,
                    InvalidKeyTypeException

Throws:

java.io.IOException

KeyNotFoundException

InvalidKeyTypeException

addKey

public void addKey(java.lang.Comparable key,
                   int record)
            throws java.io.IOException,
                   KeyAlreadyExistException,
                   InvalidKeyTypeException,
                   KeyTooLongException

Add a key to the index

Throws:

java.io.IOException

KeyAlreadyExistException

InvalidKeyTypeException

KeyTooLongException

getDepth

public int getDepth()
             throws java.io.IOException

Calculate the depth for the index

Throws:

java.io.IOException

isUnique

public boolean isUnique()

Contains this index unique values?

toString

public java.lang.String toString()