Struct BTreeTable

pub struct BTreeTable {
    pub key_field: usize,
    pub tuple_scheme: Schema,
    /* private fields */
}

B+ Tree

Fields

key_field: usize

tuple_scheme: Schema

Implementations

impl BTreeTable

pub fn new(file_path: &str, key_field: usize, row_scheme: &Schema) -> Self

impl BTreeTable

pub fn get_id(&self) -> u32

pub fn get_tuple_scheme(&self) -> Schema

pub fn tuples_count(&self) -> usize

Calculate the number of tuples in the table. Require S_LOCK on all pages.

pub fn get_random_tuple(&self, _tx: &Transaction) -> Tuple

impl BTreeTable

pub fn insert_tuple(&self, tx: &Transaction, tuple: &Tuple) -> SmallResult

Insert a tuple into this BTreeFile, keeping the tuples in sorted order. May cause pages to split if the page where tuple belongs is full.

pub fn split_leaf_page( &self, tx: &Transaction, page_rc: Arc<RwLock<BTreeLeafPage>>, field: IntField, ) -> ResultPod<BTreeLeafPage>

Split a leaf page to make room for new tuples and recursively split the parent node as needed to accommodate a new entry. The new entry should have a key matching the key field of the first tuple in the right-hand page (the key is “copied up”), and child pointers pointing to the two leaf pages resulting from the split. Update sibling pointers and parent pointers as needed.

Return the leaf page into which a new tuple with key field “field” should be inserted.

Arguments

field: the key field of the tuple to be inserted after the split is complete. Necessary to know which of the two pages to return.

pub fn get_empty_page_index(&self, tx: &Transaction) -> u32

impl BTreeTable

pub fn get_page(&self)

Method to encapsulate the process of locking/fetching a page. First the method checks the local cache (“dirtypages”), and if it can’t find the requested page there, it fetches it from the buffer pool. It also adds pages to the dirtypages cache if they are fetched with read-write permission, since presumably they will soon be dirtied by this transaction.

This method is needed to ensure that page updates are not lost if the same pages are accessed multiple times.

reference:

• https://sourcegraph.com/github.com/XiaochenCui/small-db-hw@87607789b677d6afee00a223eacb4f441bd4ae87/-/blob/src/java/smalldb/BTreeFile.java?L551&subtree=true

impl BTreeTable

pub fn set_root_pid(&self, tx: &Transaction, root_pid: &BTreePageID)

pub fn get_file(&self) -> MutexGuard<'_, File>

pub fn write_empty_page_to_disk(&self, page_id: &BTreePageID)

pub fn write_page_to_disk(&self, page_id: &BTreePageID, data: &Vec<u8>)

pub fn get_first_page( &self, tx: &Transaction, perm: Permission, ) -> Arc<RwLock<BTreeLeafPage>>

pub fn get_last_page( &self, tx: &Transaction, perm: Permission, ) -> Arc<RwLock<BTreeLeafPage>>

pub fn get_root_pid(&self, tx: &Transaction) -> BTreePageID

Get the root page pid.

pub fn get_root_ptr_page( &self, tx: &Transaction, ) -> Arc<RwLock<BTreeRootPointerPage>>

pub fn pages_count(&self) -> usize

The count of pages in this BTreeFile

(the ROOT_POINTER page is not included)

pub fn get_first_tuple(&self, _pid: &BTreePageID) -> Option<Tuple>

pub fn set_page_index(&self, i: u32)

pub fn get_last_tuple( &self, tx: &Transaction, pid: &BTreePageID, ) -> Option<WrappedTuple>

impl BTreeTable

debug methods

pub fn draw_tree(&self, max_level: i32)

Print the BTreeFile structure.

Arguments

• max_level - the max level of the print
  • 0: print the root pointer page
  • 1: print the root pointer page and the root page (internal or leaf)
  • …
  • -1: print all pages

pub fn check_integrity(&self, check_occupancy: bool)

checks the integrity of the tree:

• parent pointers.
• sibling pointers.
• range invariants.
• record to page pointers.
• occupancy invariants. (if enabled)

require s_lock on all pages.

panic on any error found.

impl BTreeTable

delete-related methods

pub fn delete_tuple( &self, tx: &Transaction, tuple: &WrappedTuple, ) -> SmallResult

Delete a tuple from this BTreeFile.

May cause pages to merge or redistribute entries/tuples if the pages become less than half full.

Trait Implementations

impl Display for BTreeTable

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.