Top Description Fields Constructors Methods
org.apache.derby.impl.store.access.btree

public abstract Class BTree

extends GenericConglomerate
Class Inheritance
Known Direct Subclasses
org.apache.derby.impl.store.access.btree.index.B2I
Imports
org.apache.derby.shared.common.reference.SQLState, org.apache.derby.iapi.services.io.FormatableBitSet, .FormatIdUtil, .Storable, org.apache.derby.shared.common.sanity.SanityManager, org.apache.derby.shared.common.error.StandardException, org.apache.derby.iapi.store.access.conglomerate.TransactionManager, org.apache.derby.iapi.store.access.ConglomerateController, .DynamicCompiledOpenConglomInfo, .RowLocationRetRowSource, .StaticCompiledOpenConglomInfo, org.apache.derby.iapi.store.raw.LockingPolicy, .RawStoreFactory, .ContainerHandle, .Transaction, .ContainerKey, org.apache.derby.iapi.types.DataValueDescriptor, org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil, .GenericConglomerate, .OpenConglomerateScratchSpace, .TemplateRow, java.io.IOException, .ObjectOutput, .ObjectInput, java.util.Properties

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.

Field Summary

Modifier and TypeField and Description
pack-priv boolean
allowDuplicates

Whether the index allows duplicates or not.

protected boolean[]
protected int[]
collation_ids

The array of collation id's for each column in the template.

protected int
conglom_format_id

Format id of the conglomerate.

protected int[]
format_ids

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

protected boolean
hasCollatedTypes

Tells if there is at least one column in the conglomerate whose collation isn't StringDataValue.COLLATION_TYPE_UCS_BASIC.

protected ContainerKey
id

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

pack-priv boolean
maintainParentLinks

Whether the parent should maintain links from child pages to their parent.

pack-priv static int
maxRowsPerPage

Maximum rows per page to place on a btree leaf or nonleaf page.

protected int
nKeyFields

The number of key fields.

pack-priv int
nUniqueColumns

The number of uniqueness columns.

public static final String
public static final String
PROPERTY_MAX_ROWS_PER_PAGE_PARAMETER

Property name for the maximum number of rows to place in a btree page (leaf or branch).

public static final String
public static final String
public static final String
public static final String
public static final long
ROOTPAGEID

The page number of the root page is always at the fixed page number: ROOTPAGEID.

pack-priv boolean
uniqueWithDuplicateNulls

Attribute to indicate the index allows duplicate only in case of keys with no part null.

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
public void
addColumn(TransactionManager
Transaction to associate the lock with.
xact_manager
,
int
The column number to add this column at.
column_id
,
Storable
An instance of the column to be added to table.
template_column
,
int
Collation id of the added column.
collation_id
)

Implements org.apache.derby.iapi.store.access.conglomerate.Conglomerate.addColumn.

Add a column to the conglomerate.

public void
create(Transaction rawtran, int segmentId, long input_containerid, DataValueDescriptor[] template, Properties properties, int conglom_format_id, int tmpFlag)

Do the generic part of creating a b-tree conglomerate.

pack-priv final DataValueDescriptor[]

Returns:

The new template.
createBranchTemplate
(Transaction rawtran, DataValueDescriptor page_ptr)

Create a branch row template for this conglomerate.

public final DataValueDescriptor[]

Returns:

The new template.
createTemplate
(Transaction rawtran)

Create a template for this conglomerate.

public abstract void
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.

public long
public DynamicCompiledOpenConglomInfo

Returns:

The dynamic information.
getDynamicCompiledConglomInfo
()

Implements org.apache.derby.iapi.store.access.conglomerate.Conglomerate.getDynamicCompiledConglomInfo.

Return dynamic information about the conglomerate to be dynamically reused in repeated execution of a statement.

public final ContainerKey

Returns:

The ContainerKey.
getId
()

Implements org.apache.derby.iapi.store.access.conglomerate.Conglomerate.getId.

Get the id of the container of the conglomerate.

public boolean
isNull()

Implements org.apache.derby.iapi.services.io.Storable.isNull.

Return whether the value is null or not.

public boolean

Returns:

whether conglomerate is temporary or not.
isTemporary
()

Implements org.apache.derby.iapi.store.access.conglomerate.Conglomerate.isTemporary.

Is this conglomerate temporary?

public final boolean
isUnique()

Is this a "unique" index?

public boolean

Returns:

is index type is uniqueWithDuplicateNulls
isUniqueWithDuplicateNulls
()

Returns if the index type is uniqueWithDuplicateNulls.

public abstract long
load(TransactionManager
The TransactionController under which this operation takes place.
xact_manager
,
boolean
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.
createConglom
,
RowLocationRetRowSource
Where the rows come from.
rowSource
)

Redeclares org.apache.derby.iapi.store.access.conglomerate.Conglomerate.load.

Load a b-tree.

public abstract ConglomerateController
lockTable(TransactionManager
Transaction to associate the lock with.
xact_manager
,
int open_mode, int lock_level, int isolation_level)

Lock the base table.

public abstract ConglomerateController
open(TransactionManager
The access xact to associate all ops on cc with.
xact_manager
,
Transaction
The raw store xact to associate all ops on cc with.
rawtran
,
boolean hold, int
A bit mask of TransactionController.MODE_* bits, indicating info about the open.
open_mode
,
int
Either TransactionController.MODE_TABLE or TransactionController.MODE_RECORD, as passed into the openConglomerate() call.
lock_level
,
LockingPolicy
The LockingPolicy to use to open the conglomerate.
locking_policy
,
StaticCompiledOpenConglomInfo static_info, DynamicCompiledOpenConglomInfo dynamic_info)

Redeclares org.apache.derby.iapi.store.access.conglomerate.Conglomerate.open.

Open a b-tree controller.

public void
readExternal(ObjectInput
the stream to read data from in order to restore the object
in
)

Implements java.io.Externalizable.readExternal.

Restore the in-memory representation from the stream.

public void
restoreToNull()

Implements org.apache.derby.iapi.services.io.Storable.restoreToNull.

Restore the in-memory representation to the null value.

public void
setUniqueWithDuplicateNulls(boolean
true if the index will be unique only for non null keys
uniqueWithDuplicateNulls
)

Set if the index is unique only for non null keys

public String
toString()

Overrides java.lang.Object.toString.

Public toString() Method:

public void
writeExternal(ObjectOutput
the stream to write the object to
out
)

Implements java.io.Externalizable.writeExternal.

Store the stored representation of the column value in the stream.

Inherited from org.apache.derby.impl.store.access.conglomerate.GenericConglomerate:
cloneValuecomparegetLengthgetNewNullgetObjectgetStringgetTypeNamehasCollatedColumnssetFromsetValueFromResultSet

Field Detail

allowDuplicatesback to summary
pack-priv boolean allowDuplicates

Whether the index allows duplicates or not.

ascDescInfoback to summary
protected boolean[] ascDescInfo
collation_idsback to summary
protected int[] collation_ids

The array of collation id's for each column in the template.

conglom_format_idback to summary
protected int conglom_format_id

Format id of the conglomerate.

format_idsback to summary
protected int[] format_ids

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

hasCollatedTypesback to summary
protected boolean hasCollatedTypes

Tells if there is at least one column in the conglomerate whose collation isn't StringDataValue.COLLATION_TYPE_UCS_BASIC.

idback to summary
protected ContainerKey id

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

maxRowsPerPageback to summary
pack-priv 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.

nKeyFieldsback to summary
protected int nKeyFields

The number of key fields.

nUniqueColumnsback to summary
pack-priv int nUniqueColumns

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

PROPERTY_ALLOWDUPLICATESback to summary
public static final String PROPERTY_ALLOWDUPLICATES
PROPERTY_MAX_ROWS_PER_PAGE_PARAMETERback to summary
public static final 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_NKEYFIELDSback to summary
public static final String PROPERTY_NKEYFIELDS
PROPERTY_NUNIQUECOLUMNSback to summary
public static final String PROPERTY_NUNIQUECOLUMNS
PROPERTY_UNIQUE_WITH_DUPLICATE_NULLSback to summary
public static final String PROPERTY_UNIQUE_WITH_DUPLICATE_NULLS
ROOTPAGEIDback to summary
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.

uniqueWithDuplicateNullsback to summary
pack-priv boolean uniqueWithDuplicateNulls

Attribute to indicate the index allows duplicate only in case of keys with no part null. This attribute has no effect if unique is true. If unique is false and isUniqueWithDuplicateNulls is set to true the index will allow duplicates of any key with at least one column null, but for non null keys will act like a unique index.

Constructor Detail

BTreeback to summary
public BTree()

Method Detail

addColumnback to summary
public void addColumn(TransactionManager xact_manager, int column_id, Storable template_column, int collation_id) throws StandardException

Implements org.apache.derby.iapi.store.access.conglomerate.Conglomerate.addColumn.

Add a column to the conglomerate.

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

Parameters
xact_manager:TransactionManager

Transaction to associate the lock with.

column_id:int

The column number to add this column at.

template_column:Storable

An instance of the column to be added to table.

collation_id:int

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.addColumn.

Collation id of the added column.

Exceptions
StandardException:
Standard exception policy.
createback to summary
public void create(Transaction rawtran, int segmentId, long input_containerid, DataValueDescriptor[] template, 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. :

  • "allowDuplicates" (boolean). If set to true the table will allow rows which are duplicate in key column's 0 through (nUniqueColumns - 1). Currently only supports "false". This property is optional, defaults to false.
  • "nKeyFields" (integer) Columns 0 through (nKeyFields - 1) will be included in key of the conglomerate. This implementation requires that "nKeyFields" must be the same as the number of fields in the conglomerate, including the rowLocationColumn. Other implementations may relax this restriction to allow non-key fields in the index. This property is required.
  • "nUniqueColumns" (integer) Columns 0 through "nUniqueColumns" will be used to check for uniqueness. So for a standard SQL non-unique index implementation set "nUniqueColumns" to the same value as "nKeyFields"; and for a unique index set "nUniqueColumns" to "nKeyFields" - 1 (ie. don't include the rowLocationColumn in the uniqueness check). This property is required.
  • "maintainParentLinks" (boolean) Whether the b-tree pages maintain the page number of their parent. Only used for consistency checking. It takes a certain amount more effort to maintain these links, but they're really handy for ensuring that the index is consistent. This property is optional, defaults to true.
Exceptions
StandardException:
Thrown by underlying raw store, or thrown by this routine on an invalid containerid.
createBranchTemplateback to summary
pack-priv final DataValueDescriptor[] createBranchTemplate(Transaction rawtran, 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:DataValueDescriptor[]

The new template.

Exceptions
StandardException:
Standard exception policy.
createTemplateback to summary
public final DataValueDescriptor[] createTemplate(Transaction rawtran) 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:DataValueDescriptor[]

The new template.

Exceptions
StandardException:
Standard exception policy.
dropback to summary
public abstract void drop(TransactionManager xact_manager) throws StandardException

Redeclares org.apache.derby.iapi.store.access.conglomerate.Conglomerate.drop.

Drop this btree. This must be done by a concrete implementation.

Exceptions
StandardException:
Standard exception policy.
See Also
org.apache.derby.iapi.store.access.conglomerate.Conglomerate#drop
getBtreeLockingPolicyback to summary
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.

Exceptions
StandardException:
Standard exception policy.
getContaineridback to summary
public long getContainerid()

Implements org.apache.derby.iapi.store.access.conglomerate.Conglomerate.getContainerid.

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.getContainerid.

Get the containerid of conglomerate.

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

Returns:long

The containerid.

getDynamicCompiledConglomInfoback to summary
public DynamicCompiledOpenConglomInfo getDynamicCompiledConglomInfo() throws StandardException

Implements org.apache.derby.iapi.store.access.conglomerate.Conglomerate.getDynamicCompiledConglomInfo.

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, ...

Returns:DynamicCompiledOpenConglomInfo

The dynamic information.

Exceptions
StandardException:
Standard exception policy.
getIdback to summary
public final ContainerKey getId()

Implements org.apache.derby.iapi.store.access.conglomerate.Conglomerate.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:ContainerKey

The ContainerKey.

isNullback to summary
public boolean isNull()

Implements org.apache.derby.iapi.services.io.Storable.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:boolean

Doc from org.apache.derby.iapi.services.io.Storable.isNull.

true if the value is null and false otherwise.

See Also
org.apache.derby.iapi.services.io.Storable#isNull
isTemporaryback to summary
public boolean isTemporary()

Implements org.apache.derby.iapi.store.access.conglomerate.Conglomerate.isTemporary.

Is this conglomerate temporary?

Returns:boolean

whether conglomerate is temporary or not.

isUniqueback to summary
public final boolean isUnique()

Is this a "unique" index?

isUniqueWithDuplicateNullsback to summary
public boolean isUniqueWithDuplicateNulls()

Returns if the index type is uniqueWithDuplicateNulls.

Returns:boolean

is index type is uniqueWithDuplicateNulls

loadback to summary
public abstract long load(TransactionManager xact_manager, boolean createConglom, RowLocationRetRowSource rowSource) throws StandardException

Redeclares org.apache.derby.iapi.store.access.conglomerate.Conglomerate.load.

Load a b-tree. This must be done by a concrete implementation.

Parameters
xact_manager:TransactionManager

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.load.

The TransactionController under which this operation takes place.

createConglom:boolean

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.load.

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:RowLocationRetRowSource

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.load.

Where the rows come from.

Returns:long

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.load.

The number of rows loaded.

Exceptions
StandardException:
Standard exception policy.
See Also
org.apache.derby.iapi.store.access.conglomerate.Conglomerate#load
lockTableback to summary
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:TransactionManager

Transaction to associate the lock with.

Exceptions
StandardException:
Standard exception policy.
openback to summary
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

Redeclares org.apache.derby.iapi.store.access.conglomerate.Conglomerate.open.

Open a b-tree controller. This must be done by a concrete implementation.

Parameters
xact_manager:TransactionManager

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.open.

The access xact to associate all ops on cc with.

rawtran:Transaction

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.open.

The raw store xact to associate all ops on cc with.

open_mode:int

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.open.

A bit mask of TransactionController.MODE_* bits, indicating info about the open.

lock_level:int

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.open.

Either TransactionController.MODE_TABLE or TransactionController.MODE_RECORD, as passed into the openConglomerate() call.

locking_policy:LockingPolicy

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.open.

The LockingPolicy to use to open the conglomerate.

Returns:ConglomerateController

Doc from org.apache.derby.iapi.store.access.conglomerate.Conglomerate.open.

The open ConglomerateController.

Exceptions
StandardException:
Standard exception policy.
See Also
org.apache.derby.iapi.store.access.conglomerate.Conglomerate#open
readExternalback to summary
public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException

Implements java.io.Externalizable.readExternal.

Restore the in-memory representation from the stream.

Parameters
in:ObjectInput

Doc from java.io.Externalizable.readExternal.

the stream to read data from in order to restore the object

Exceptions
IOException:
thrown by readObject()
ClassNotFoundException:
Thrown if the stored representation is serialized and a class named in the stream could not be found.
See Also
java.io.Externalizable#readExternal
restoreToNullback to summary
public void restoreToNull()

Implements org.apache.derby.iapi.services.io.Storable.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
org.apache.derby.iapi.services.io.Storable#restoreToNull
setUniqueWithDuplicateNullsback to summary
public void setUniqueWithDuplicateNulls(boolean uniqueWithDuplicateNulls)

Set if the index is unique only for non null keys

Parameters
uniqueWithDuplicateNulls:boolean

true if the index will be unique only for non null keys

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Public toString() Method:

Returns:String

Doc from java.lang.Object.toString.

a string representation of the object

writeExternalback to summary
public void writeExternal(ObjectOutput out) throws IOException

Implements java.io.Externalizable.writeExternal.

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.

Parameters
out:ObjectOutput

Doc from java.io.Externalizable.writeExternal.

the stream to write the object to

Exceptions
IOException:
thrown by writeObject()