org.apache.derby.impl.store.access.btree
Class BTree

java.lang.Object
  extended byorg.apache.derby.iapi.types.DataType
      extended byorg.apache.derby.impl.store.access.conglomerate.GenericConglomerate
          extended byorg.apache.derby.impl.store.access.btree.BTree
All Implemented Interfaces:
CloneableObject, Conglomerate, DataValueDescriptor, java.io.Externalizable, Formatable, Orderable, java.io.Serializable, Storable, TypedFormat
Direct Known Subclasses:
B2I

public abstract class BTree
extends GenericConglomerate

A b-tree object corresponds to an instance of a b-tree conglomerate. It contains the static information about a conglomerate which is built at create conglomerate time.

This generic implementation is expected to be extended by the concreate implementations.

The fields are set when the conglomerate is created and never changed thereafter. When alter table is supported then it will change under the control of a table level lock.

They have package scope because they're read by the scans and controllers.

A table of all conglomerates in the system is maintained by the accessmanager. A cache of conglomerates is maintained in the accessmanager, and references to the read only objects are handed out. A copy of the Conglomerate object is kept in the control row of the root page, so that during logical undo this information can be read without needing to access the possibly corrupt table maintained by the access manager.

See Also:
Serialized Form

Field Summary
(package private)  boolean allowDuplicates
          Whether the index allows duplicates or not.
protected  boolean[] ascDescInfo
           
protected  int conglom_format_id
          Format id of the conglomerate.
(package private)  int[] format_ids
          The array of format id's, one for each column in the template.
protected  ContainerKey id
          The id of the container in which this b-tree is stored.
(package private)  boolean maintainParentLinks
          Whether the parent should maintain links from child pages to their parent.
(package private) static int maxRowsPerPage
          Maximum rows per page to place on a btree leaf or nonleaf page.
protected  int nKeyFields
          The number of key fields.
(package private)  int nUniqueColumns
          The number of uniqueness columns.
static java.lang.String PROPERTY_ALLOWDUPLICATES
           
static java.lang.String PROPERTY_MAX_ROWS_PER_PAGE_PARAMETER
          Property name for the maximum number of rows to place in a btree page (leaf or branch).
static java.lang.String PROPERTY_NKEYFIELDS
           
static java.lang.String PROPERTY_NUNIQUECOLUMNS
           
static java.lang.String PROPERTY_PARENTLINKS
           
static long ROOTPAGEID
          The page number of the root page is always at the fixed page number: ROOTPAGEID.
 
Fields inherited from interface org.apache.derby.iapi.types.Orderable
ORDER_OP_EQUALS, ORDER_OP_GREATEROREQUALS, ORDER_OP_GREATERTHAN, ORDER_OP_LESSOREQUALS, ORDER_OP_LESSTHAN
 
Constructor Summary
BTree()
           
 
Method Summary
 void addColumn(TransactionManager xact_manager, int column_id, Storable template_column)
          Add a column to the conglomerate.
 void create(Transaction rawtran, int segmentId, long input_containerid, DataValueDescriptor[] template, java.util.Properties properties, int conglom_format_id, int tmpFlag)
          Do the generic part of creating a b-tree conglomerate.
(package private)  DataValueDescriptor[] createBranchTemplate(DataValueDescriptor page_ptr)
          Create a branch row template for this conglomerate.
 DataValueDescriptor[] createTemplate()
          Create a template for this conglomerate.
abstract  void drop(TransactionManager xact_manager)
          Drop this btree.
protected abstract  BTreeLockingPolicy getBtreeLockingPolicy(Transaction rawtran, int lock_level, int mode, int isolation_level, ConglomerateController base_cc, OpenBTree open_btree)
          Create a new btree locking policy from scratch.
 long getContainerid()
          Get the containerid of conglomerate.
 DynamicCompiledOpenConglomInfo getDynamicCompiledConglomInfo(long conglomId)
          Return dynamic information about the conglomerate to be dynamically reused in repeated execution of a statement.
 ContainerKey getId()
          Get the id of the container of the conglomerate.
 boolean isNull()
          Return whether the value is null or not.
 boolean isTemporary()
          Is this conglomerate temporary?
 boolean isUnique()
          Is this a "unique" index?
abstract  long load(TransactionManager xact_manager, boolean createConglom, RowLocationRetRowSource rowSource)
          Load a b-tree.
abstract  ConglomerateController lockTable(TransactionManager xact_manager, int open_mode, int lock_level, int isolation_level)
          Lock the base table.
abstract  ConglomerateController open(TransactionManager xact_manager, Transaction rawtran, boolean hold, int open_mode, int lock_level, LockingPolicy locking_policy, StaticCompiledOpenConglomInfo static_info, DynamicCompiledOpenConglomInfo dynamic_info)
          Open a b-tree controller.
 void readExternal(java.io.ObjectInput in)
          Restore the in-memory representation from the stream.
 void readExternalFromArray(ArrayInputStream in)
          Read the DataValueDescriptor from the stream.
 void restoreToNull()
          Restore the in-memory representation to the null value.
 java.lang.String toString()
          Public toString() Method:
 void writeExternal(java.io.ObjectOutput out)
          Store the stored representation of the column value in the stream.
 
Methods inherited from class org.apache.derby.impl.store.access.conglomerate.GenericConglomerate
compare, getClone, getLength, getNewNull, getObject, getString, getTypeName, setFrom, setValue, setValueFromResultSet
 
Methods inherited from class org.apache.derby.iapi.types.DataType
checkHostVariable, cloneObject, coalesce, compare, dataTypeConversion, equals, equals, flip, genericSetObject, getBoolean, getByte, getBytes, getDate, getDouble, getFloat, getInt, getLong, getNationalString, getShort, getStream, getTime, getTimestamp, greaterOrEquals, greaterThan, in, invalidFormat, isNotNull, isNullOp, lessOrEquals, lessThan, normalize, notEquals, outOfRange, setBigDecimal, setInto, setInto, setObjectForCast, setToNull, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, throwLangSetMismatch, typePrecedence, typeToBigDecimal
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface org.apache.derby.iapi.store.access.conglomerate.Conglomerate
compressConglomerate, defragmentConglomerate, fetchMaxOnBTree, getStaticCompiledConglomInfo, openScan, openStoreCost, purgeConglomerate
 
Methods inherited from interface org.apache.derby.iapi.services.io.TypedFormat
getTypeFormatId
 
Methods inherited from interface org.apache.derby.iapi.types.DataValueDescriptor
checkHostVariable, coalesce, compare, equals, estimateMemoryUsage, getBoolean, getByte, getBytes, getDate, getDouble, getFloat, getInt, getLong, getShort, getStream, getTime, getTimestamp, greaterOrEquals, greaterThan, in, isNotNull, isNullOp, lessOrEquals, lessThan, normalize, notEquals, setBigDecimal, setInto, setInto, setObjectForCast, setToNull, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, typePrecedence, typeToBigDecimal
 

Field Detail

ROOTPAGEID

public static final long ROOTPAGEID
The page number of the root page is always at the fixed page number: ROOTPAGEID. This means that given an open container, during logical undo one can always find the root page and look up the conglomerate information.

See Also:
Constant Field Values

PROPERTY_MAX_ROWS_PER_PAGE_PARAMETER

public static final java.lang.String PROPERTY_MAX_ROWS_PER_PAGE_PARAMETER
Property name for the maximum number of rows to place in a btree page (leaf or branch). Equal to 'derby.access.btreeMaxRowPerPage'. Used by tests and debugging to exactly control split points, and to make it easier to test tall trees without needing lots of data.


PROPERTY_ALLOWDUPLICATES

public static final java.lang.String PROPERTY_ALLOWDUPLICATES
See Also:
Constant Field Values

PROPERTY_NKEYFIELDS

public static final java.lang.String PROPERTY_NKEYFIELDS
See Also:
Constant Field Values

PROPERTY_NUNIQUECOLUMNS

public static final java.lang.String PROPERTY_NUNIQUECOLUMNS
See Also:
Constant Field Values

PROPERTY_PARENTLINKS

public static final java.lang.String PROPERTY_PARENTLINKS
See Also:
Constant Field Values

id

protected ContainerKey id
The id of the container in which this b-tree is stored.


nKeyFields

protected int nKeyFields
The number of key fields.


nUniqueColumns

int nUniqueColumns
The number of uniqueness columns. These are the columns that are considered for the purpose of detecting duplicate keys and rows.


allowDuplicates

boolean allowDuplicates
Whether the index allows duplicates or not.


maintainParentLinks

boolean maintainParentLinks
Whether the parent should maintain links from child pages to their parent. These links are only used for consistency checking purposes. They improve consistency checking at the cost of run-time efficiency.


maxRowsPerPage

static int maxRowsPerPage
Maximum rows per page to place on a btree leaf or nonleaf page. Used by testing to finely control split points. Only changed for debugging purposes. RESOLVE (mikem) - this should not be static. Need to design a way in debugging mode to get btree created with a persistent "maxRowsPerPage". This hack makes all btrees get created with the "last" maxRowsPerPage value set.


conglom_format_id

protected int conglom_format_id
Format id of the conglomerate.


format_ids

int[] format_ids
The array of format id's, one for each column in the template.


ascDescInfo

protected boolean[] ascDescInfo
Constructor Detail

BTree

public BTree()
Method Detail

getBtreeLockingPolicy

protected abstract BTreeLockingPolicy getBtreeLockingPolicy(Transaction rawtran,
                                                            int lock_level,
                                                            int mode,
                                                            int isolation_level,
                                                            ConglomerateController base_cc,
                                                            OpenBTree open_btree)
                                                     throws StandardException
Create a new btree locking policy from scratch.

Throws:
StandardException - Standard exception policy.

lockTable

public abstract ConglomerateController lockTable(TransactionManager xact_manager,
                                                 int open_mode,
                                                 int lock_level,
                                                 int isolation_level)
                                          throws StandardException
Lock the base table.

Assumes that segment of the base container is the same as the segment of the btree segment.

RESOLVE - we really want to get the lock without opening the container. raw store will be providing this.

Parameters:
xact_manager - Transaction to associate the lock with.
Throws:
StandardException - Standard exception policy.

createBranchTemplate

final DataValueDescriptor[] createBranchTemplate(DataValueDescriptor page_ptr)
                                          throws StandardException
Create a branch row template for this conglomerate.

Reads the format id's of each of the columns and manufactures object of the given type for each. It then uses these "empty" objects to create a template row. The object passed in is then added to the last column of the row.

Returns:
The new template.
Throws:
StandardException - Standard exception policy.

createTemplate

public final DataValueDescriptor[] createTemplate()
                                           throws StandardException
Create a template for this conglomerate.

Reads the format id's of each of the columns and manufactures object of the given type for each. It then uses these "empty" objects to create a template row.

This method is public so that B2IUndo() can call it.

Returns:
The new template.
Throws:
StandardException - Standard exception policy.

isUnique

public final boolean isUnique()
Is this a "unique" index?


addColumn

public void addColumn(TransactionManager xact_manager,
                      int column_id,
                      Storable template_column)
               throws StandardException
Add a column to the conglomerate.

Currently B2I does not support this operation. input template column.

Parameters:
xact_manager - Transaction to associate the lock with.
column_id - The column number to add this column at.
template_column - An instance of the column to be added to table.
Throws:
StandardException - Standard exception policy.

getId

public final ContainerKey getId()
Get the id of the container of the conglomerate.

Will have to change when a conglomerate could have more than one container. The ContainerKey is a combination of the container id and segment id.

Returns:
The ContainerKey.

create

public void create(Transaction rawtran,
                   int segmentId,
                   long input_containerid,
                   DataValueDescriptor[] template,
                   java.util.Properties properties,
                   int conglom_format_id,
                   int tmpFlag)
            throws StandardException
Do the generic part of creating a b-tree conglomerate. This method is called from the concrete subclass (which may also read some properties).

This method processes all properties which are generic to all BTree's. It creates the container for the btree.

The following properties are generic to a b-tree conglomerate. :

Throws:
StandardException - Thrown by underlying raw store, or thrown by this routine on an invalid containerid.

drop

public abstract void drop(TransactionManager xact_manager)
                   throws StandardException
Drop this btree. This must be done by a concrete implementation.

Throws:
StandardException - Standard exception policy.
See Also:
Conglomerate.drop(org.apache.derby.iapi.store.access.conglomerate.TransactionManager)

load

public abstract long load(TransactionManager xact_manager,
                          boolean createConglom,
                          RowLocationRetRowSource rowSource)
                   throws StandardException
Load a b-tree. This must be done by a concrete implementation.

Parameters:
xact_manager - The TransactionController under which this operation takes place.
createConglom - If true, the conglomerate is being created in the same operation as the openAndLoadConglomerate. The enables further optimization as recovery does not require page allocation to be logged.
rowSource - Where the rows come from.
Returns:
The number of rows loaded.
Throws:
StandardException - Standard exception policy.
See Also:
Conglomerate.load(org.apache.derby.iapi.store.access.conglomerate.TransactionManager, boolean, org.apache.derby.iapi.store.access.RowLocationRetRowSource)

getContainerid

public long getContainerid()
Description copied from interface: Conglomerate
Get the containerid of conglomerate.

Will have to change when a conglomerate could have more than one containerid.

Returns:
The containerid.

getDynamicCompiledConglomInfo

public DynamicCompiledOpenConglomInfo getDynamicCompiledConglomInfo(long conglomId)
                                                             throws StandardException
Return dynamic information about the conglomerate to be dynamically reused in repeated execution of a statement.

The dynamic info is a set of variables to be used in a given ScanController or ConglomerateController. It can only be used in one controller at a time. It is up to the caller to insure the correct thread access to this info. The type of info in this is a scratch template for btree traversal, other scratch variables for qualifier evaluation, ...

Parameters:
conglomId - The identifier of the conglomerate to open.
Returns:
The dynamic information.
Throws:
StandardException - Standard exception policy.

isTemporary

public boolean isTemporary()
Is this conglomerate temporary?

Returns:
whether conglomerate is temporary or not.

open

public abstract ConglomerateController open(TransactionManager xact_manager,
                                            Transaction rawtran,
                                            boolean hold,
                                            int open_mode,
                                            int lock_level,
                                            LockingPolicy locking_policy,
                                            StaticCompiledOpenConglomInfo static_info,
                                            DynamicCompiledOpenConglomInfo dynamic_info)
                                     throws StandardException
Open a b-tree controller. This must be done by a concrete implementation.

Parameters:
xact_manager - The access xact to associate all ops on cc with.
rawtran - The raw store xact to associate all ops on cc with.
open_mode - A bit mask of TransactionController.MODE_* bits, indicating info about the open.
lock_level - Either TransactionController.MODE_TABLE or TransactionController.MODE_RECORD, as passed into the openConglomerate() call.
locking_policy - The LockingPolicy to use to open the conglomerate.
Returns:
The open ConglomerateController.
Throws:
StandardException - Standard exception policy.
See Also:
Conglomerate.open(org.apache.derby.iapi.store.access.conglomerate.TransactionManager, org.apache.derby.iapi.store.raw.Transaction, boolean, int, int, org.apache.derby.iapi.store.raw.LockingPolicy, org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo, org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo)

isNull

public boolean isNull()
Return whether the value is null or not. The containerid being zero is what determines nullness; subclasses are not expected to override this method.

Returns:
true if the value is null and false otherwise.
See Also:
Storable.isNull()

restoreToNull

public void restoreToNull()
Restore the in-memory representation to the null value. The containerid being zero is what determines nullness; subclasses are not expected to override this method.

See Also:
Storable.restoreToNull()

readExternal

public void readExternal(java.io.ObjectInput in)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException
Restore the in-memory representation from the stream.

Throws:
java.lang.ClassNotFoundException - Thrown if the stored representation is serialized and a class named in the stream could not be found.
java.io.IOException - thrown by readObject()
See Also:
Externalizable.readExternal(java.io.ObjectInput)

readExternalFromArray

public void readExternalFromArray(ArrayInputStream in)
                           throws java.io.IOException,
                                  java.lang.ClassNotFoundException
Description copied from interface: DataValueDescriptor
Read the DataValueDescriptor from the stream.

Initialize the data value by reading it's values from the ArrayInputStream. This interface is provided as a way to achieve possible performance enhancement when reading an array can be optimized over reading from a generic stream from readExternal().

Parameters:
in - The array stream positioned at the beginning of the byte stream to read from.
Throws:
java.lang.ClassNotFoundException - If a necessary class can not be found while reading the object from the stream.
java.io.IOException - Usual error is if you try to read past limit on the stream.

writeExternal

public void writeExternal(java.io.ObjectOutput out)
                   throws java.io.IOException
Store the stored representation of the column value in the stream. It might be easier to simply store the properties - which would certainly make upgrading easier.

Throws:
java.io.IOException - thrown by writeObject()

toString

public java.lang.String toString()
Public toString() Method:


Built on Tue 2006-10-10 19:23:47+0200, from revision exported

Apache Derby V10.1 Engine Documentation - Copyright © 1997,2005 The Apache Software Foundation or its licensors, as applicable.