Classes
class	bt_cursor_t
	A cursor object to sequentially read BTree. More...

class	btree_m

class	btree_impl
	The internal implementation class which actually implements the functions of btree_m. More...

class	btree_page_data
	This class holds B-tree-specific headers as well as an ordered list of items. More...

class	btrec_t
	Represents a record in BTree. More...

class	btree_page_h
	Page handle for B-Tree data page. More...

class	ss_m
	This is the SHORE Storage Manager API. More...

Functions
static rc_t	btree_m::defrag_page (btree_page_h &page)
	Defrags the given page to remove holes and ghost records in the page. More...

static rc_t	ss_m::create_index (StoreID &stid)
	Create a B+-Tree index. More...

static rc_t	ss_m::destroy_index (const StoreID &iid)
	Destroy a B+-Tree index. More...

static rc_t	ss_m::touch_index (StoreID stid, uint64_t &page_count)
	Touches all pages in the B-tree index to load them into bufferpool. More...

static rc_t	ss_m::create_assoc (StoreID stid, const w_keystr_t &key, const vec_t &el)
	Create an entry in a B+-Tree index. More...

static rc_t	ss_m::update_assoc (StoreID stid, const w_keystr_t &key, const vec_t &el)
	Update record data of an entry in a B+-Tree index. More...

static rc_t	ss_m::put_assoc (StoreID stid, const w_keystr_t &key, const vec_t &el)
	Put record data of an entry in a B+-Tree index. More...

static rc_t	ss_m::overwrite_assoc (StoreID stid, const w_keystr_t &key, const char *el, smsize_t offset, smsize_t elen)
	This function finds the given key, updates the specific part of element if found. More...

static rc_t	ss_m::destroy_assoc (StoreID stid, const w_keystr_t &key)
	Remove an entry from a B+-Tree index. More...

static rc_t	ss_m::find_assoc (StoreID stid, const w_keystr_t &key, void *el, smsize_t &elen, bool &found)
	Find an entry associated with a key in a B+-Tree index. More...

static rc_t	ss_m::defrag_index_page (btree_page_h &page)
	Defrags the given page to remove holes and ghost records in the page. More...

static rc_t	ss_m::verify_index (StoreID stid, int hash_bits, bool &consistent)
	Verifies the integrity of B-Tree index using the fence-key bitmap technique. More...

Detailed Description

The storage manager supports B+-Tree indexes provide associative access to data by associating keys with values in 1:1 or many:1 relationships.

The number of key-value pairs that an index can hold is limited by the space available on the volume containing the index. The combined sizes of the key (i.e., the number of actual data bytes it contains) and value must be less than or equal to max_entry_size, which is a function of the page size, and is such that two entries of this size fit on a page along with all the page and entry metadata. See sm_config_info_t and ss_m::config_info.

The minimum size of a B-Tree index is 8 pages (1 extent).

Function Documentation

§ create_assoc()

rc_t ss_m::create_assoc	(	StoreID	stid,
		const w_keystr_t &	key,
		const vec_t &	el
	)

static

Create an entry in a B+-Tree index.

Parameters

[in]	stid	ID of the index.
[in]	key	Key for the association to be created.
[in]	el	Element for the association to be created.

The combined sizes of the key (i.e., the number of actual data bytes it contains; that is key.get_length_as_keystr()-1) and element vectors must be less than or equal to max_entry_size.

§ create_index()

rc_t ss_m::create_index ( StoreID & stid )

static

Create a B+-Tree index.

Parameters

[out] stid New store ID will be returned here.

§ defrag_index_page()

rc_t ss_m::defrag_index_page ( btree_page_h & page )

static

Defrags the given page to remove holes and ghost records in the page.

A page can have unused holes between records and ghost records as a result of inserts and deletes. This method removes those dead spaces to compress the page. The best thing of this is that we have to log only the slot numbers of ghost records that are removed because there are 'logically' no changes. Context: System transaction.

Parameters

[in] page the page to be defraged

§ defrag_page()

rc_t btree_m::defrag_page ( btree_page_h & page )

static

Defrags the given page to remove holes and ghost records in the page.

A page can have unused holes between records and ghost records as a result of inserts and deletes. This method removes those dead spaces to compress the page. The best thing of this is that we have to log only the slot numbers of ghost records that are removed because there are 'logically' no changes. Context: System transaction.

Parameters

[in] page the page to be defraged

§ destroy_assoc()

rc_t ss_m::destroy_assoc	(	StoreID	stid,
		const w_keystr_t &	key
	)

static

Remove an entry from a B+-Tree index.

Parameters

[in]	stid	ID of the index.
[in]	key	Key of the entry to be removed.

§ destroy_index()

rc_t ss_m::destroy_index ( const StoreID & iid )

static

Destroy a B+-Tree index.

Parameters

[in] iid ID of the index to be destroyed.

§ find_assoc()

rc_t ss_m::find_assoc	(	StoreID	stid,
		const w_keystr_t &	key,
		void *	el,
		smsize_t &	elen,
		bool &	found
	)

static

Find an entry associated with a key in a B+-Tree index.

Parameters

[in]	stid	ID of the index.
[in]	key	Key of the entries to be removed.
[out]	el	Element associated with the given key will be copied into this buffer.
[in]	elen	Length of buffer into which the result will be written. If too small, eRECWONTFIT will be returned. Length of result will be returned here.
[out]	found	True if an entry is found.

If the index is not unique (allows duplicates), the first element found with the given key will be returned.

§ overwrite_assoc()

rc_t ss_m::overwrite_assoc	(	StoreID	stid,
		const w_keystr_t &	key,
		const char *	el,
		smsize_t	offset,
		smsize_t	elen
	)

static

This function finds the given key, updates the specific part of element if found.

Parameters

[in]	stid	id of root page
[in]	key	key of the existing tuple
[in]	el	new data of the tuple
[in]	offset	overwrites to this position of the record
[in]	elen	number of bytes to overwrite

§ put_assoc()

rc_t ss_m::put_assoc	(	StoreID	stid,
		const w_keystr_t &	key,
		const vec_t &	el
	)

static

Put record data of an entry in a B+-Tree index.

Parameters

[in]	stid	ID of the index.
[in]	key	Key for the association to be created or replaced.
[in]	el	New element for the association.

§ touch_index()

rc_t ss_m::touch_index	(	StoreID	stid,
		uint64_t &	page_count
	)

static

Touches all pages in the B-tree index to load them into bufferpool.

skip

Parameters

[in]	stid	ID of the index to be touched.
[out]	page_count	Number of pages touched.

This is mainly for performance experiments with hot bufferpool. We traditionally used a cursor to touch all pages, but this one is much more efficient for the purpose.

§ update_assoc()

rc_t ss_m::update_assoc	(	StoreID	stid,
		const w_keystr_t &	key,
		const vec_t &	el
	)

static

Update record data of an entry in a B+-Tree index.

Parameters

[in]	stid	ID of the index.
[in]	key	Key for the association to be replaced.
[in]	el	New element for the association.

§ verify_index()

rc_t ss_m::verify_index	(	StoreID	stid,
		int	hash_bits,
		bool &	consistent
	)

static

Verifies the integrity of B-Tree index using the fence-key bitmap technique.

This method constructs a bitmap, traverses all pages in this BTree and flips each bit based on facts collected from each page. The size of bitmap is 2^hash_bits bits = 2^(hash_bits - 3) bytes. We recommend hash_bits to be around 20. For more details of this algorithm, check out TODS'11 paper. Context: in both user and system transaction.

Note: This method holds a tree-wide read latch/lock. No concurrent update is allowed.

Parameters

[in]	stid	ID of the index.
[in]	hash_bits	the number of bits we use for hashing, at most 31.
[out]	consistent	whether the BTree is consistent

Classes

Functions

Detailed Description

Function Documentation

§ create_assoc()

§ create_index()

§ defrag_index_page()

§ defrag_page()

§ destroy_assoc()

§ destroy_index()

§ find_assoc()

§ overwrite_assoc()

§ put_assoc()

§ touch_index()

§ update_assoc()

§ verify_index()