simpledb.index.btree
Class BTreeIndex

java.lang.Object
  simpledb.index.btree.BTreeIndex

All Implemented Interfaces:

Index

public class BTreeIndex
extends Object
implements Index

A B-tree implementation of the Index interface.

Author:

Edward Sciore

Constructor Summary

BTreeIndex(String idxname, Schema leafsch, Transaction tx)
Opens a B-tree index for the specified index.

Method Summary

void	beforeFirst(Constant searchkey) Traverses the directory to find the leaf block corresponding to the specified search key.
void	close() Closes the index by closing its open leaf page, if necessary.
void	delete(Constant dataval, RID datarid) Deletes the specified index record.
RID	getDataRid() Returns the dataRID value from the current leaf record.
void	insert(Constant dataval, RID datarid) Inserts the specified record into the index.
boolean	next() Moves to the next leaf record having the previously-specified search key.
static int	searchCost(int numblocks, int rpb) Estimates the number of block accesses required to find all index records having a particular search key.

Methods inherited from class java.lang.Object

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

Constructor Detail

BTreeIndex

public BTreeIndex(String idxname,
                  Schema leafsch,
                  Transaction tx)

Opens a B-tree index for the specified index. The method determines the appropriate files for the leaf and directory records, creating them if they did not exist.

Parameters:

idxname - the name of the index

leafsch - the schema of the leaf index records

tx - the calling transaction

Method Detail

beforeFirst

public void beforeFirst(Constant searchkey)

Traverses the directory to find the leaf block corresponding to the specified search key. The method then opens a page for that leaf block, and positions the page before the first record (if any) having that search key. The leaf page is kept open, for use by the methods next and getDataRid.

Specified by:

beforeFirst in interface Index

Parameters:

searchkey - the search key value.

See Also:

Index.beforeFirst(simpledb.query.Constant)

next

public boolean next()

Moves to the next leaf record having the previously-specified search key. Returns false if there are no more such leaf records.

Specified by:

next in interface Index

Returns:

false if no other index records have the search key.

See Also:

Index.next()

getDataRid

public RID getDataRid()

Returns the dataRID value from the current leaf record.

Specified by:

getDataRid in interface Index

Returns:

the dataRID stored in the current index record.

See Also:

Index.getDataRid()

insert

public void insert(Constant dataval,
                   RID datarid)

Inserts the specified record into the index. The method first traverses the directory to find the appropriate leaf page; then it inserts the record into the leaf. If the insertion causes the leaf to split, then the method calls insert on the root, passing it the directory entry of the new leaf page. If the root node splits, then makeNewRoot is called.

Specified by:

insert in interface Index

Parameters:

dataval - the dataval in the new index record.

datarid - the dataRID in the new index record.

See Also:

Index.insert(simpledb.query.Constant, simpledb.record.RID)

delete

public void delete(Constant dataval,
                   RID datarid)

Deletes the specified index record. The method first traverses the directory to find the leaf page containing that record; then it deletes the record from the page.

Specified by:

delete in interface Index

Parameters:

dataval - the dataval of the deleted index record

datarid - the dataRID of the deleted index record

See Also:

Index.delete(simpledb.query.Constant, simpledb.record.RID)

close

public void close()

Closes the index by closing its open leaf page, if necessary.

Specified by:

close in interface Index

See Also:

Index.close()

searchCost

public static int searchCost(int numblocks,
                             int rpb)

Estimates the number of block accesses required to find all index records having a particular search key.

Parameters:

numblocks - the number of blocks in the B-tree directory

rpb - the number of index entries per block

Returns:

the estimated traversal cost