#include <btree.h>

Inheritance diagram for btree_m:

Public Member Functions
	btree_m ()

	~btree_m ()

void	construct_once ()

void	destruct_once ()

Static Public Member Functions
static smsize_t	max_entry_size ()

static rc_t	create (StoreID stid, PageID root)

static rc_t	insert (StoreID store, const w_keystr_t &key, const cvec_t &elem)

static rc_t	update (StoreID store, const w_keystr_t &key, const cvec_t &elem)

static rc_t	put (StoreID store, const w_keystr_t &key, const cvec_t &elem)

static rc_t	overwrite (StoreID store, const w_keystr_t &key, const char *el, smsize_t offset, smsize_t elen)

static rc_t	remove (StoreID store, const w_keystr_t &key)

static void	print (const PageID &root, bool print_elem=true)

static rc_t	touch_all (StoreID stid, uint64_t &page_count)

static rc_t	touch (const btree_page_h &page, uint64_t &page_count)

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

static rc_t	lookup (StoreID store, const w_keystr_t &key_to_find, void *el, smsize_t &elen, bool &found)

static rc_t	get_du_statistics (const PageID &root_pid, btree_stats_t &btree_stats, bool audit)

static rc_t	verify_tree (StoreID store, int hash_bits, bool &consistent)

static rc_t	verify_volume (int hash_bits, verify_volume_result &result)
	Verifies consistency of all BTree indexes in the volume. More...

Static Protected Member Functions
static rc_t	remove_as_undo (StoreID store, const w_keystr_t &key)

static rc_t	update_as_undo (StoreID store, const w_keystr_t &key, const cvec_t &elem)

static rc_t	overwrite_as_undo (StoreID store, const w_keystr_t &key, const char *el, smsize_t offset, smsize_t elen)

static rc_t	undo_ghost_mark (StoreID store, const w_keystr_t &key)

Static Private Member Functions
static rc_t	is_empty (StoreID store, bool &ret)

static rc_t	_get_du_statistics_recurse (const PageID &currentpid, btree_stats_t &_stats, base_stat_t &lf_cnt, base_stat_t &int_cnt, btree_lf_stats_t &lf_stats, btree_int_stats_t &int_stats, bool audit)

Friends
class	btree_page_h

class	btree_impl

class	bt_cursor_t

class	btree_remove_log

class	btree_insert_log

class	btree_insert_nonghost_log

class	btree_update_log

class	btree_overwrite_log

class	btree_ghost_mark_log

class	btree_ghost_reclaim_log

Detailed Description

Data access API for B+Tree.

Constructor & Destructor Documentation

§ btree_m()

btree_m::btree_m ( )

inline

§ ~btree_m()

btree_m::~btree_m ( )

inline

Member Function Documentation

§ _get_du_statistics_recurse()

static rc_t btree_m::_get_du_statistics_recurse	(	const PageID &	currentpid,
		btree_stats_t &	_stats,
		base_stat_t &	lf_cnt,
		base_stat_t &	int_cnt,
		btree_lf_stats_t &	lf_stats,
		btree_int_stats_t &	int_stats,
		bool	audit
	)

staticprivate

Used by get_du_statistics internally to collect all nodes' statistics.

§ construct_once()

void btree_m::construct_once ( )

§ create()

rc_t btree_m::create	(	StoreID	stid,
		PageID	root
	)

static

Create a btree. Return the root page id in root.

§ destruct_once()

void btree_m::destruct_once ( )

§ get_du_statistics()

static rc_t btree_m::get_du_statistics	(	const PageID &	root_pid,
		btree_stats_t &	btree_stats,
		bool	audit
	)

static

§ insert()

rc_t btree_m::insert	(	StoreID	store,
		const w_keystr_t &	key,
		const cvec_t &	elem
	)

static

Insert <key, el> into the btree.

§ is_empty()

rc_t btree_m::is_empty	(	StoreID	store,
		bool &	ret
	)

staticprivate

Return true in ret if btree at root is empty. false otherwise.

§ lookup()

rc_t btree_m::lookup	(	StoreID	store,
		const w_keystr_t &	key_to_find,
		void *	el,
		smsize_t &	elen,
		bool &	found
	)

static

Find key in btree. If found, copy up to elen bytes of the entry element into el.

§ max_entry_size()

smsize_t btree_m::max_entry_size ( )

static

§ overwrite()

rc_t btree_m::overwrite	(	StoreID	store,
		const w_keystr_t &	key,
		const char *	el,
		smsize_t	offset,
		smsize_t	elen
	)

static

Update specific part of el of key with the new data.

§ overwrite_as_undo()

rc_t btree_m::overwrite_as_undo	(	StoreID	store,
		const w_keystr_t &	key,
		const char *	el,
		smsize_t	offset,
		smsize_t	elen
	)

staticprotected

§ print()

void btree_m::print	(	const PageID &	root,
		bool	print_elem = `true`
	)

static

Print the btree (for debugging only).

§ put()

rc_t btree_m::put	(	StoreID	store,
		const w_keystr_t &	key,
		const cvec_t &	elem
	)

static

Put <key, el> into the btree; if key didn't exist, inserts it, otherwise updates el of key with the new data.

§ remove()

rc_t btree_m::remove	(	StoreID	store,
		const w_keystr_t &	key
	)

static

Remove key from the btree.

§ remove_as_undo()

rc_t btree_m::remove_as_undo	(	StoreID	store,
		const w_keystr_t &	key
	)

staticprotected

§ touch()

rc_t btree_m::touch	(	const btree_page_h &	page,
		uint64_t &	page_count
	)

static

§ touch_all()

rc_t btree_m::touch_all	(	StoreID	stid,
		uint64_t &	page_count
	)

static

Touch all pages in the btree (for performance experiments).

§ undo_ghost_mark()

rc_t btree_m::undo_ghost_mark	(	StoreID	store,
		const w_keystr_t &	key
	)

staticprotected

§ update()

rc_t btree_m::update	(	StoreID	store,
		const w_keystr_t &	key,
		const cvec_t &	elem
	)

static

Update el of key with the new data.

§ update_as_undo()

rc_t btree_m::update_as_undo	(	StoreID	store,
		const w_keystr_t &	key,
		const cvec_t &	elem
	)

staticprotected

§ verify_tree()

rc_t btree_m::verify_tree	(	StoreID	store,
		int	hash_bits,
		bool &	consistent
	)

static

Verifies the integrity of whole tree 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]	store	Store ID
[in]	hash_bits	the number of bits we use for hashing, at most 31.
[out]	consistent	whether the BTree is consistent

§ verify_volume()

rc_t btree_m::verify_volume	(	int	hash_bits,
		verify_volume_result &	result
	)

static

Verifies consistency of all BTree indexes in the volume.

Unlike verify_index() this method sequentially scans all pages in this volume to efficiently conduct the batch-verification. However, you cannot have concurrent update operations while you are running this verification. It might cause deadlocks! To allow concurrent transaction while verifying, consider using _ux_verify_tree().

Parameters

[in]	hash_bits	the number of bits we use for hashing per BTree, at most 31.
[out]	result	Results of the verification.

See also: _ux_verify_tree()

Friends And Related Function Documentation

§ bt_cursor_t

friend class bt_cursor_t

friend

§ btree_ghost_mark_log

friend class btree_ghost_mark_log

friend

§ btree_ghost_reclaim_log

friend class btree_ghost_reclaim_log

friend

§ btree_impl

friend class btree_impl

friend

§ btree_insert_log

friend class btree_insert_log

friend

§ btree_insert_nonghost_log

friend class btree_insert_nonghost_log

friend

§ btree_overwrite_log

friend class btree_overwrite_log

friend

§ btree_page_h

friend class btree_page_h

friend

§ btree_remove_log

friend class btree_remove_log

friend

§ btree_update_log

friend class btree_update_log

friend

The documentation for this class was generated from the following files:

src/sm/btree.h
src/sm/btree.cpp

Public Member Functions

Static Public Member Functions

Static Protected Member Functions

Static Private Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

§ btree_m()

§ ~btree_m()

Member Function Documentation

§ _get_du_statistics_recurse()

§ construct_once()

§ create()

§ destruct_once()

§ get_du_statistics()

§ insert()

§ is_empty()

§ lookup()

§ max_entry_size()

§ overwrite()

§ overwrite_as_undo()

§ print()

§ put()

§ remove()

§ remove_as_undo()

§ touch()

§ touch_all()

§ undo_ghost_mark()

§ update()

§ update_as_undo()

§ verify_tree()

§ verify_volume()

Friends And Related Function Documentation

§ bt_cursor_t

§ btree_ghost_mark_log

§ btree_ghost_reclaim_log

§ btree_impl

§ btree_insert_log

§ btree_insert_nonghost_log

§ btree_overwrite_log

§ btree_page_h

§ btree_remove_log

§ btree_update_log