Class BTree
- java.lang.Object
-
- org.apache.derby.iapi.types.DataType
-
- org.apache.derby.impl.store.access.conglomerate.GenericConglomerate
-
- org.apache.derby.impl.store.access.btree.BTree
-
- All Implemented Interfaces:
java.io.Externalizable
,java.io.Serializable
,java.lang.Comparable
,Formatable
,Storable
,TypedFormat
,Conglomerate
,DataValueDescriptor
,Orderable
- 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
Fields Modifier and Type Field Description (package private) boolean
allowDuplicates
Whether the index allows duplicates or not.protected boolean[]
ascDescInfo
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.(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 java.lang.String
PROPERTY_UNIQUE_WITH_DUPLICATE_NULLS
static long
ROOTPAGEID
The page number of the root page is always at the fixed page number: ROOTPAGEID.(package private) boolean
uniqueWithDuplicateNulls
Attribute to indicate the index allows duplicate only in case of keys with no part null.-
Fields inherited from interface org.apache.derby.iapi.types.DataValueDescriptor
UNKNOWN_LOGICAL_LENGTH
-
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
Constructors Constructor Description BTree()
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description void
addColumn(TransactionManager xact_manager, int column_id, Storable template_column, int collation_id)
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(Transaction rawtran, DataValueDescriptor page_ptr)
Create a branch row template for this conglomerate.DataValueDescriptor[]
createTemplate(Transaction rawtran)
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()
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?boolean
isUniqueWithDuplicateNulls()
Returns if the index type is uniqueWithDuplicateNulls.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
restoreToNull()
Restore the in-memory representation to the null value.void
setUniqueWithDuplicateNulls(boolean uniqueWithDuplicateNulls)
Set if the index is unique only for non null keysjava.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
cloneValue, compare, getLength, getNewNull, getObject, getString, getTypeName, hasCollatedColumns, setFrom, setValueFromResultSet
-
Methods inherited from class org.apache.derby.iapi.types.DataType
checkHostVariable, cloneHolder, coalesce, compare, compare, compare, compareTo, dataTypeConversion, equals, equals, flip, getBoolean, getByte, getBytes, getDate, getDouble, getFloat, getInt, getLong, getShort, getStream, getTime, getTimestamp, getTraceString, greaterOrEquals, greaterThan, hasStream, in, invalidFormat, isNotNull, isNullOp, lessOrEquals, lessThan, normalize, notEquals, outOfRange, readExternalFromArray, recycle, setBigDecimal, setInto, setInto, setObjectForCast, setToNull, setValue, setValue, setValue, 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.types.DataValueDescriptor
checkHostVariable, cloneHolder, coalesce, compare, compare, compare, equals, estimateMemoryUsage, getBoolean, getByte, getBytes, getDate, getDouble, getFloat, getInt, getLong, getShort, getStream, getTime, getTimestamp, getTraceString, greaterOrEquals, greaterThan, hasStream, in, isNotNull, isNullOp, lessOrEquals, lessThan, normalize, notEquals, readExternalFromArray, recycle, setBigDecimal, setInto, setInto, setObjectForCast, setToNull, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, setValue, typePrecedence, typeToBigDecimal
-
Methods inherited from interface org.apache.derby.iapi.services.io.TypedFormat
getTypeFormatId
-
-
-
-
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
-
PROPERTY_UNIQUE_WITH_DUPLICATE_NULLS
public static final java.lang.String PROPERTY_UNIQUE_WITH_DUPLICATE_NULLS
- 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.
-
uniqueWithDuplicateNulls
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.
-
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
protected int[] format_ids
The array of format id's, one for each column in the template.
-
ascDescInfo
protected boolean[] ascDescInfo
-
collation_ids
protected int[] collation_ids
The array of collation id's for each column in the template.
-
hasCollatedTypes
protected boolean hasCollatedTypes
Tells if there is at least one column in the conglomerate whose collation isn't StringDataValue.COLLATION_TYPE_UCS_BASIC.
-
-
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(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:
- The new template.
- Throws:
StandardException
- Standard exception policy.
-
createTemplate
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:
- The new template.
- Throws:
StandardException
- Standard exception policy.
-
isUnique
public final boolean isUnique()
Is this a "unique" index?
-
setUniqueWithDuplicateNulls
public void setUniqueWithDuplicateNulls(boolean uniqueWithDuplicateNulls)
Set if the index is unique only for non null keys- Parameters:
uniqueWithDuplicateNulls
- true if the index will be unique only for non null keys
-
isUniqueWithDuplicateNulls
public boolean isUniqueWithDuplicateNulls()
Returns if the index type is uniqueWithDuplicateNulls.- Returns:
- is index type is uniqueWithDuplicateNulls
-
addColumn
public void addColumn(TransactionManager xact_manager, int column_id, Storable template_column, int collation_id) 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.collation_id
- Collation id of the added column.- 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. :
- "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.
- 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() 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, ...
- 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)
-
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:- Overrides:
toString
in classjava.lang.Object
-
-