001: /*
002: * $Id: BaseBTree.java,v 1.22 2005/12/20 18:32:42 ahimanikya Exp $
003: * =======================================================================
004: * Copyright (c) 2002-2005 Axion Development Team. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * 1. Redistributions of source code must retain the above
011: * copyright notice, this list of conditions and the following
012: * disclaimer.
013: *
014: * 2. Redistributions in binary form must reproduce the above copyright
015: * notice, this list of conditions and the following disclaimer in
016: * the documentation and/or other materials provided with the
017: * distribution.
018: *
019: * 3. The names "Tigris", "Axion", nor the names of its contributors may
020: * not be used to endorse or promote products derived from this
021: * software without specific prior written permission.
022: *
023: * 4. Products derived from this software may not be called "Axion", nor
024: * may "Tigris" or "Axion" appear in their names without specific prior
025: * written permission.
026: *
027: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
028: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
029: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
030: * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
031: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
032: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
033: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
034: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
035: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
036: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
037: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
038: * =======================================================================
039: */
040:
041: package org.axiondb.util;
042:
043: import java.io.File;
044: import java.io.IOException;
045:
046: import org.apache.commons.collections.primitives.ArrayIntList;
047: import org.apache.commons.collections.primitives.IntList;
048: import org.axiondb.engine.rowcollection.IntHashMap;
049:
050: /**
051: * A b-tree is a balanced, multi-way search tree that assumes its data is stored on disk.
052: * The b-tree structure is designed to minimize the number of disk accesses by storing
053: * data in a broad, short tree and reading each node in one gulp.
054: * <p />
055: * Each b-tree node (excluding the root) contains at least <i>t </i>-1 and at most 2 <i>t
056: * </i>-1 keys (and their associated values) (where <i>t </i> is the "minimization
057: * factor") in non-decreasing order. Associated with each key <i>k(i) </i> is a reference
058: * to a subtree containing all keys greater than <i>k(i-1) </i> and less than or equal to
059: * <i>k(i) </i>. An "extra" subtree reference contains all keys greater than the maximum
060: * key in this node.
061: *
062: * @version $Revision: 1.22 $ $Date: 2005/12/20 18:32:42 $
063: * @author Chuck Burdick
064: * @author Dave Pekarek Krohn
065: * @author Rodney Waldhoff
066: */
067: abstract class BaseBTree {
068: // NB: We are aware that declaring methods as final doesn't improve performance in
069: // general.The stuff declared final is declared final so that we know it's not
070: // overriden in any subclass. This makes refactoring easier.
071:
072: protected BaseBTree(BTreeMetaData meta) throws IOException,
073: ClassNotFoundException {
074: _metaData = meta;
075: setValues(new ArrayIntList(getMinimizationFactor() - 1));
076: setChildIds(new ArrayIntList(getMinimizationFactor()));
077: }
078:
079: /**
080: * @param dir the directory to store my data files in
081: * @param name the name of this btree structure (used to generate data file names)
082: * @param minimizationFactor the minimization factor (often <i>t </i>). Each node will
083: * contain at most 2 <i>t </i>-1 keys, and 2 <i>t </i> children.
084: * @param root the root of my tree (or null if this node is going to be the root).
085: */
086: protected BaseBTree(File dir, String name, int minimizationFactor)
087: throws IOException, ClassNotFoundException {
088: _metaData = new BTreeMetaData(dir, name, minimizationFactor,
089: this );
090: setValues(new ArrayIntList(getMinimizationFactor() - 1));
091: setChildIds(new ArrayIntList(getMinimizationFactor()));
092: }
093:
094: public abstract void save() throws IOException,
095: ClassNotFoundException;
096:
097: /**
098: * Saves the tree. It saves the counter file and {@link #write}s any dirty nodes.
099: */
100: public void save(File dataDirectory) throws IOException,
101: ClassNotFoundException {
102: getBTreeMetaData().setDataDirectory(dataDirectory);
103: if (getBTreeMetaData().hasDirtyNodes()) {
104: getBTreeMetaData().saveCounter();
105: }
106: for (IntHashMap.ValueIterator iter = getBTreeMetaData()
107: .getDirtyNodes(); iter.hasNext();) {
108: BaseBTree tree = (BaseBTree) iter.next();
109: tree.write();
110: iter.remove();
111: }
112: }
113:
114: public void saveAfterTruncate() throws IOException,
115: ClassNotFoundException {
116: getBTreeMetaData().setAllClean();
117: save();
118: }
119:
120: public abstract int size();
121:
122: public void truncate() {
123: getValues().clear();
124: getChildIds().clear();
125: }
126:
127: /**
128: * Add a reference to the given file id. Flags me as dirty.
129: */
130: protected final void addFileId(int fileId) {
131: getChildIds().add(fileId);
132: getBTreeMetaData().setDirty(this );
133: }
134:
135: /**
136: * Store a reference to the given file id at the specifed index. Flags me as dirty.
137: */
138: protected final void addFileId(int index, int fileid) {
139: getChildIds().add(index, fileid);
140: getBTreeMetaData().setDirty(this );
141: }
142:
143: /**
144: * Add the given specified file ids. Flags me as dirty.
145: */
146: protected final void addFileIds(IntList fileIds) {
147: getChildIds().addAll(fileIds);
148: getBTreeMetaData().setDirty(this );
149: }
150:
151: /**
152: * Clear my values and file ids. Flags me as dirty.
153: */
154: protected void clearData() {
155: getValues().clear();
156: getChildIds().clear();
157: getBTreeMetaData().setDirty(this );
158: }
159:
160: protected final BTreeMetaData getBTreeMetaData() {
161: return _metaData;
162: }
163:
164: protected final IntList getChildIds() {
165: return _childIds;
166: }
167:
168: protected final int getFileId() {
169: return _fileId;
170: }
171:
172: /**
173: * Get the file id for the specified index.
174: */
175: protected final int getFileIdForIndex(int index) {
176: return getChildIds().get(index);
177: }
178:
179: /**
180: * Return the maximum number of keys I can contain (2*
181: * {@link #getMinimizationFactor minimizationFactor}-1).
182: */
183: protected final int getKeyCapacity() {
184: return (2 * getMinimizationFactor()) - 1;
185: }
186:
187: protected final int getMinimizationFactor() {
188: return _metaData.getMinimizationFactor();
189: }
190:
191: protected final int getValue(int index) {
192: return _vals.get(index);
193: }
194:
195: protected final IntList getValues() {
196: return _vals;
197: }
198:
199: protected final boolean isFull() {
200: return size() == getKeyCapacity();
201: }
202:
203: /** Returns <code>true</code> iff I don't contain any child nodes. */
204: protected final boolean isLeaf() {
205: return (getChildIds().isEmpty());
206: }
207:
208: /** Returns <code>true</code> iff I am the root node. */
209: protected final boolean isRoot() {
210: return _metaData.isRoot(this );
211: }
212:
213: protected abstract void read() throws IOException,
214: ClassNotFoundException;
215:
216: protected final void saveCounterIfRoot() throws IOException {
217: if (isRoot()) {
218: _metaData.saveCounter();
219: }
220: }
221:
222: protected final void setChildIds(IntList childIds) {
223: _childIds = childIds;
224: }
225:
226: protected final void setFileId(int fileId) {
227: _fileId = fileId;
228: }
229:
230: protected final void setValue(int index, int val) {
231: _vals.set(index, val);
232: }
233:
234: protected final void setValues(IntList vals) {
235: _vals = vals;
236: }
237:
238: /**
239: * Return a String comprised of 2*n spaces.
240: */
241: protected final String space(int n) {
242: StringBuffer buf = new StringBuffer(0);
243: for (int i = 0; i < n; i++) {
244: buf.append(" ");
245: }
246: return buf.toString();
247: }
248:
249: protected abstract void write() throws IOException,
250: ClassNotFoundException;
251:
252: /** The file ids of my children. */
253: private IntList _childIds = null;
254: /** The idenentifier for my data file. */
255: private int _fileId = 0;
256:
257: private BTreeMetaData _metaData = null;
258: /** The row ids corresponding to each of my keys. */
259: private IntList _vals = null;
260: }
|