Package edu.caltech.nanodb.storage.btreefile

Class BTreeFileVerifier

java.lang.Object

edu.caltech.nanodb.storage.btreefile.BTreeFileVerifier

public class BTreeFileVerifier
extends Object

This class provides some simple verification operations for B⁺ tree tuple files.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	BTreeFileVerifier.PageInfo	This helper class is used to keep track of details of pages within the B+ tree file.
private static class	BTreeFileVerifier.ScanAbortedException	This runtime exception class is used to abort the verification scan.

Field Summary

Fields

Modifier and Type	Field	Description
private DBFile	dbFile	The actual DBFile object backing the tuple-file, since it is used so frequently in the verification.
private ArrayList<String>	errors	The collection of errors found during the verification process.
private static org.apache.logging.log4j.Logger	logger	A logging object for reporting anything interesting that happens.
private HashMap<Integer,BTreeFileVerifier.PageInfo>	pages	This collection maps individual B+ tree pages to the details that the verifier collects for each page.
private StorageManager	storageManager	A reference to the storage manager since we use it so much.
private BTreeTupleFile	tupleFile	The B+ tree tuple file to verify.

Constructor Summary

Constructors

Constructor	Description
BTreeFileVerifier(StorageManager storageManager, BTreeTupleFile tupleFile)	Initialize a verifier object to verify a specific B+ tree tuple file.

Method Summary

Modifier and Type	Method	Description
private void	pass1ScanThruAllPages()	This method implements pass 1 of the verification process: scanning through all pages in the tuple file, collecting basic details about each page.
private void	pass2TreeScanThruFile()	This method implements pass 2 of the verification process: performing a tree-scan through the entire tuple file, starting with the root page of the file.
private void	pass3ScanThruLeafList()
private void	pass4ScanThruEmptyList()
private void	pass5ExaminePageReachability()
private void	scanTree(int pageNo, int parentPageNo, Tuple parentLeftKey, Tuple parentRightKey)	This helper function traverses the B+ tree structure, verifying various invariants that should hold on the file structure.
List<String>	verify()	This method is the entry-point for the verification process.

Methods inherited from class java.lang.Object

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

Field Details

logger

private static org.apache.logging.log4j.Logger logger

A logging object for reporting anything interesting that happens.

storageManager

private StorageManager storageManager

A reference to the storage manager since we use it so much.

tupleFile

private BTreeTupleFile tupleFile

The B⁺ tree tuple file to verify.

dbFile

private DBFile dbFile

The actual DBFile object backing the tuple-file, since it is used so frequently in the verification.

pages

private HashMap<Integer,BTreeFileVerifier.PageInfo> pages

This collection maps individual B⁺ tree pages to the details that the verifier collects for each page.

errors

private ArrayList<String> errors

The collection of errors found during the verification process.

Constructor Details

BTreeFileVerifier

public BTreeFileVerifier(StorageManager storageManager,
 BTreeTupleFile tupleFile)

Initialize a verifier object to verify a specific B⁺ tree tuple file.

Method Details

verify

public List<String> verify()

This method is the entry-point for the verification process. It performs multiple passes through the file structure to identify various issues. Any errors that are identified are returned in the collection of error messages.

Returns:

a list of error messages describing issues found with the tuple file's structure. If no errors are detected, this will be an empty list, not null.

pass1ScanThruAllPages

private void pass1ScanThruAllPages()

This method implements pass 1 of the verification process: scanning through all pages in the tuple file, collecting basic details about each page.

pass2TreeScanThruFile

private void pass2TreeScanThruFile()

This method implements pass 2 of the verification process: performing a tree-scan through the entire tuple file, starting with the root page of the file.

scanTree

private void scanTree(int pageNo,
 int parentPageNo,
 Tuple parentLeftKey,
 Tuple parentRightKey)

This helper function traverses the B⁺ tree structure, verifying various invariants that should hold on the file structure.

pass3ScanThruLeafList

private void pass3ScanThruLeafList()

pass4ScanThruEmptyList

private void pass4ScanThruEmptyList()

pass5ExaminePageReachability

private void pass5ExaminePageReachability()