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

#include <btree_page_h.h>

Inheritance diagram for btree_page_h:

Classes
union	record_info_int16_convert

union	record_info_shpid_convert

Public Member Functions
	btree_page_h ()

	btree_page_h (const btree_page_h &p)

	~btree_page_h ()

btree_page_h &	operator= (btree_page_h &p)

PageID	btree_root () const

smsize_t	used_space () const

smsize_t	usable_space () const

int	level () const
	Returns 1 if leaf, >1 if non-leaf. More...

PageID	pid0 () const
	Returns left-most ptr (used only in non-leaf nodes). More...

PageID	pid0_opaqueptr () const
	Returns left-most opaque pointer (used only in non-leaf nodes). More...

PageID	root () const
	Returns root page; used for recovery. More...

bool	is_leaf () const
	Is associated page a leaf? More...

bool	is_node () const
	Returns if this page is NOT a leaf. More...

bool	is_leaf_parent () const

PageID	get_foster () const
	Returns ID of B-link page (0 if not linked). More...

PageID	get_foster_opaqueptr () const
	Returns opaque pointer of B-link page (0 if not linked). More...

const char *	get_prefix_key () const
	Returns the prefix which is removed from all entries in this page. More...

int16_t	get_prefix_length () const
	Returns the length of prefix key (0 means no prefix compression). More...

const char *	get_fence_low_key () const
	Returns the low fence key, which is same OR smaller than all entries in this page and its descendants. More...

int16_t	get_fence_low_length () const
	Returns the length of low fence key. More...

void	copy_fence_low_key (w_keystr_t &buffer) const
	Constructs w_keystr_t object containing the low-fence key of this page. More...

bool	is_fence_low_infimum () const
	Returns if the low-fence key is infimum. More...

const char *	get_fence_high_key_noprefix () const

int16_t	get_fence_high_length () const
	Returns the length of high fence key with prefix. More...

int16_t	get_fence_high_length_noprefix () const
	Returns the length of high fence key without prefix. More...

void	copy_fence_high_key (w_keystr_t &buffer) const
	Constructs w_keystr_t object containing the low-fence key of this page. More...

bool	is_fence_high_supremum () const
	Returns if the high-fence key is supremum. More...

const char *	get_chain_fence_high_key () const
	Returns the high fence key of foster chain. More...

int16_t	get_chain_fence_high_length () const
	Returns the length of high fence key of foster chain. More...

void	copy_chain_fence_high_key (w_keystr_t &buffer) const
	Constructs w_keystr_t object containing the low-fence key of this page. More...

bool	fence_contains (const w_keystr_t &key) const

int	compare_with_fence_low (const w_keystr_t &key) const

int	compare_with_fence_low (const char *key, size_t key_len) const
	overload for char*. More...

int	compare_with_fence_low_noprefix (const char *key, size_t key_len) const
	used when the prefix part is already checked key/key_len must be WITHOUT prefix. More...

int	compare_with_fence_high (const w_keystr_t &key) const

int	compare_with_fence_high (const char *key, size_t key_len) const
	overload for char*. More...

int	compare_with_fence_high_noprefix (const char *key, size_t key_len) const
	used when the prefix part is already checked key/key_len must be WITHOUT prefix. More...

int	compare_with_chain_fence_high (const w_keystr_t &key) const

int	compare_with_chain_fence_high (const char *key, size_t key_len) const
	overload for char*. More...

void	accept_empty_child (lsn_t new_lsn, PageID new_page_id, const bool f_redo)

rc_t	format_foster_child (btree_page_h &parent, const PageID &new_page_id, const w_keystr_t &triggering_key, w_keystr_t &split_key, int &move_count)
	Initialize the page as a foster child of the given parent. More...

bool	set_foster_child (PageID foster_child_pid, const w_keystr_t &new_fence_high, const w_keystr_t &child_fence_chain)
	Sets the given page ID as foster child of this page. More...

void	delete_range (int from, int to)

rc_t	format_steal (lsn_t new_lsn, const PageID &pid, StoreID store, PageID root, int level, PageID pid0, lsn_t pid0_emlsn, PageID foster, lsn_t foster_emlsn, const w_keystr_t &fence_low, const w_keystr_t &fence_high, const w_keystr_t &chain_fence_high, bool log_it=true, btree_page_h steal_src1=nullptr, int steal_from1=0, int steal_to1=0, btree_page_h steal_src2=nullptr, int steal_from2=0, int steal_to2=0, bool steal_src2_pid0=false, const bool full_logging=false, const bool log_src_1=false, const bool ghost=false)
	Initializes the associated page, stealing records from other pages as specified. More...

void	_steal_records (btree_page_h *steal_src, int steal_from, int steal_to, const bool full_logging)
	Steal records from steal_src. Called by format_steal. More...

rc_t	init_fence_keys (const bool set_low, const w_keystr_t &low, const bool set_high, const w_keystr_t &high, const bool set_chain, const w_keystr_t &chain_fence_high, const bool set_pid0, const PageID new_pid0, const bool set_emlsn, const lsn_t new_pid0_emlsn, const bool set_foster, const PageID foster_pid0, const bool set_foster_emlsn, const lsn_t foster_emlsn, const int remove_count=0)

rc_t	norecord_split (PageID foster, lsn_t foster_emlsn, const w_keystr_t &fence_high, const w_keystr_t &chain_fence_high)

bool	check_chance_for_norecord_split (const w_keystr_t &key_to_insert) const
	Returns if whether we can do norecord insert now. More...

int	nrecs () const
	Returns the number of records in this page. More...

int	nghosts () const
	Returns the number of ghosts records in this page. More...

bool	is_ghost (slotid_t slot) const
	Returns if the specified record is a ghost record. More...

void	get_key (slotid_t slot, w_keystr_t &key) const
	Retrieves key from given record #. More...

const char *	element (int slot, smsize_t &len, bool &ghost) const

bool	copy_element (int slot, char *out_buffer, smsize_t &len, bool &ghost) const

PageID	child (slotid_t slot) const
	Return the (non-opaque) child pointer of record in slot. More...

PageID	child_opaqueptr (slotid_t slot) const
	Return the opaque child pointer of record in slot. More...

PageID *	page_pointer_address (int offset)

size_t	get_rec_space (int slot) const

int16_t	calculate_prefix_length (int16_t existing_prefix_len, w_keystr_t low_key, w_keystr_t high_key)

rc_t	copy_records (const int rec_count, char *data_buffer, smsize_t &len)

rc_t	insert_records_dest_redo (const int16_t prefix_len, const int32_t move_count, const int16_t record_data_len, const char *record_data)

void	search (const w_keystr_t &key, bool &found_key, slotid_t &return_slot) const

void	search (const char *key_raw, size_t key_raw_len, bool &found_key, slotid_t &return_slot) const

void	search_node (const w_keystr_t &key, slotid_t &return_slot) const

rc_t	insert_node (const w_keystr_t &key, slotid_t slot, PageID child, const lsn_t &child_emlsn)

void	mark_ghost (slotid_t slot)

void	unmark_ghost (slotid_t slot)

rc_t	replace_ghost (const w_keystr_t &key, const cvec_t &elem, bool redo=false)

rc_t	replace_fence_rec_nolog_may_defrag (const w_keystr_t &low, const w_keystr_t &high, const w_keystr_t &chain, int new_prefix_length=-1)
	Replaces the special fence record with the given new data, expanding the slot length if needed. More...

rc_t	replace_fence_rec_nolog_no_defrag (const w_keystr_t &low, const w_keystr_t &high, const w_keystr_t &chain, int new_prefix_length)

rc_t	remove_shift_nolog (slotid_t slot)

rc_t	replace_el_nolog (slotid_t slot, const cvec_t &elem)

void	overwrite_el_nolog (slotid_t slot, smsize_t offset, const char *new_el, smsize_t elen)

void	reserve_ghost (const w_keystr_t &key, size_t element_length)

void	reserve_ghost (const char *key_raw, size_t key_raw_len, size_t element_length)

void	insert_nonghost (const w_keystr_t &key, const cvec_t &elem)

bool	_is_enough_spacious_ghost (const w_keystr_t &key, slotid_t slot, const cvec_t &el)

bool	check_space_for_insert_leaf (const w_keystr_t &trunc_key, const cvec_t &el)

bool	check_space_for_insert_leaf (size_t trunc_key_length, size_t element_length)

bool	check_space_for_insert_node (const w_keystr_t &key)
	for intermediate node (no element). More...

void	suggest_fence_for_split (w_keystr_t &mid, slotid_t &right_begins_from, const w_keystr_t &triggering_key) const
	Suggests a new fence key, assuming this page is being split. More...

w_keystr_t	recalculate_fence_for_split (slotid_t right_begins_from) const
	For recovering the separator key from boundary place. More...

bool	is_insertion_extremely_skewed_right () const

bool	is_insertion_skewed_right () const

bool	is_insertion_skewed_left () const

rc_t	defrag (const bool full_logging_redo=false)
	Defrags this page to remove holes and ghost records in the page. More...

rc_t	compress (const w_keystr_t &low, const w_keystr_t &high, const w_keystr_t &chain, bool redo=false)
	Compress page by trying to expand the prefix and truncate keys even further. More...

rc_t	leaf_stats (btree_lf_stats_t &btree_lf)
	stats for leaf nodes. More...

rc_t	int_stats (btree_int_stats_t &btree_int)
	stats for interior nodes. More...

void	print (bool print_elem=false)
	Debugs out the contents of this page. More...

bool	is_consistent (bool check_keyorder=false, bool check_space=false) const

lsn_t *	emlsn_address (general_recordid_t pos)

const lsn_t &	get_emlsn_general (general_recordid_t pos) const

void	set_emlsn_general (general_recordid_t pos, const lsn_t &lsn)
	Sets the Expected Child LSN of pid0, foster-child, or real child. More...

const lsn_t &	get_foster_emlsn () const

const lsn_t &	get_pid0_emlsn () const

Public Member Functions inherited from fixable_page_h
	fixable_page_h ()
	Create handle not yet fixed to a page. More...

	~fixable_page_h ()

fixable_page_h &	operator= (fixable_page_h &p)

bool	is_fixed () const
	Do we have an associated page? More...

void	unfix (bool evict=false)

bool	is_bufferpool_managed () const
	Is this page really fixed in bufferpool or a psuedo-fix? More...

w_rc_t	fix_nonroot (const fixable_page_h &parent, PageID pid, latch_mode_t mode, bool conditional=false, bool virgin_page=false, bool only_if_hit=false)

w_rc_t	fix_direct (PageID pid, latch_mode_t mode, bool conditional=false, bool virgin_page=false, bool only_if_hit=false, bool do_recovery=true)

bf_idx	pin_for_refix ()

w_rc_t	refix_direct (bf_idx idx, latch_mode_t mode, bool conditional=false)

w_rc_t	fix_root (StoreID store, latch_mode_t mode, bool conditional=false, bool virgin=false)

void	fix_nonbufferpool_page (generic_page *s)

bool	is_dirty () const

void	update_page_lsn (const lsn_t &lsn) const
	Updates page_lsn field stored in CB of buffered page. More...

lsn_t	get_page_lsn () const

uint32_t	get_log_volume ()
	returns log volume in the CB More...

void	increment_log_volume (uint32_t)

void	reset_log_volume ()

bool	has_check_recovery ()
	return value of _check_recovery flag on CB More...

void	set_img_page_lsn (const lsn_t &lsn)
	Updates lsn field inside generic_page (i.e., in the page image) More...

bool	is_to_be_deleted ()

w_rc_t	set_to_be_deleted (bool log_it)

void	unset_to_be_deleted ()

void	set_check_recovery (bool)

void	set_tag (page_tag_t tag)

latch_mode_t	latch_mode () const

bool	is_latched () const
	Do we hold our page's latch in SH or EX mode? More...

bool	change_possible_after_fix () const

bool	upgrade_latch_conditional (latch_mode_t mode=LATCH_EX)

bool	has_children () const

int	max_child_slot () const

PageID *	child_slot_address (int child_slot) const

PageID	root () const

void	setup_for_restore (generic_page *pp)

bool	is_pinned_for_restore ()

Public Member Functions inherited from generic_page_h
	generic_page_h (generic_page *s)

virtual	~generic_page_h ()

generic_page *	get_generic_page () const
	return pointer to underlying page More...

PageID	pid () const

StoreID	store () const

page_tag_t	tag () const

const lsn_t &	lsn () const

Static Public Attributes
static smsize_t	max_entry_size

Static Public Attributes inherited from fixable_page_h
static int	force_Q_fixing = 0

Private Types
enum	{ data_sz = btree_page::data_sz, hdr_sz = btree_page::hdr_sz }

enum	_internal { max_key_length = (1 << (sizeof(key_length_t) * 8 - 1)) - 1 }

typedef uint16_t	key_length_t
	A field to hold a B-tree key length. More...

typedef key_length_t	pack_scratch_t
	type of scratch space needed by _pack_leaf_record More...

typedef uint16_t	poor_man_key
	Poor man's normalized key type. More...

Private Member Functions
btree_page *	page () const

void	_pack_node_record (cvec_t &out, const cvec_t &trunc_key, const lsn_t &emlsn) const

void	_pack_leaf_record (cvec_t &out, pack_scratch_t &out_scratch, const cvec_t &trunc_key, const char *element, size_t element_len) const

void	_pack_leaf_record_prefix (cvec_t &out, pack_scratch_t &out_scratch, const cvec_t &trunc_key) const

int	_pack_fence_rec (cvec_t &out, const w_keystr_t &low, const w_keystr_t &high, const w_keystr_t &chain, int new_prefix_len) const

size_t	_predict_leaf_data_length (int trunc_key_length, int element_length) const

poor_man_key	_extract_poor_man_key (const void *trunc_key, size_t trunc_key_len) const
	Returns the value of poor-man's normalized key for the given key string WITHOUT prefix. More...

poor_man_key	_extract_poor_man_key (const cvec_t &trunc_key) const
	Returns the value of poor-man's normalized key for the given key string WITHOUT prefix. More...

poor_man_key	_extract_poor_man_key (const void *key_with_prefix, size_t key_len_with_prefix, size_t prefix_len) const
	Returns the value of poor-man's normalized key for the given key string WITH prefix. More...

poor_man_key	_poor (int slot) const
	Return poor man's key data for given slot. More...

const char *	_leaf_key_noprefix (slotid_t slot, size_t &len) const

const char *	_node_key_noprefix (slotid_t slot, size_t &len) const

size_t	_element_offset (int slot) const

int	_compare_key_noprefix (slotid_t slot, const void *key_noprefix, size_t key_len) const
	returns compare(specified-key, key_noprefix) More...

int	_compare_slot_with_key (int slot, const void *key_noprefix, size_t key_len, poor_man_key poor) const

bool	_is_consistent_keyorder () const
	internal method used from is_consistent() to check keyorder correctness. More...

bool	_is_consistent_poormankey () const
	checks if the poor-man's normalized keys are valid. More...

void	_update_btree_consecutive_skewed_insertions (slotid_t slot)
	Given the place to insert, update btree_consecutive_skewed_insertions. More...

bool	_check_space_for_insert (size_t data_length)

void	_init (lsn_t lsn, PageID page_id, StoreID store, PageID root_pid, PageID pid0, lsn_t pid0_emlsn, PageID foster_pid, lsn_t foster_emlsn, int16_t btree_level, const w_keystr_t &low, const w_keystr_t &high, const w_keystr_t &chain_fence_high, const bool ghost)

Friends
class	btree_impl

template<class T >
class	btree_ghost_t

class	btree_ghost_mark_log

class	btree_ghost_reclaim_log

template<class T >
class	page_img_format_t

class	btree_split_log

std::ostream &	operator<< (std::ostream &os, btree_page_h &b)

Additional Inherited Members
Static Public Member Functions inherited from fixable_page_h
static general_recordid_t	find_page_id_slot (generic_page *page, PageID pid)

Protected Member Functions inherited from generic_page_h
	generic_page_h (generic_page *s, const PageID &pid, page_tag_t tag, StoreID store)

Protected Attributes inherited from fixable_page_h
bool	_bufferpool_managed
	is our associated page managed by the buffer pool? More...

latch_mode_t	_mode

q_ticket_t	_Q_ticket

Protected Attributes inherited from generic_page_h
generic_page *	_pp
	The actual page we are handling; may be NULL for fixable pages. More...

Detailed Description

Page handle for B-Tree data page.

Fence Keys and B-link Tree

Our version of B-Tree header contains low-high fence keys and pointers as a b-link tree. Fence keys are NEVER changed once the page is created until the page gets splitted. Prefix compression in this scheme utilizes it by storing the common leading bytes of the two fence keys and simply getting rid of them from all entries in this page. See btree_page for the header definitions.

B-Tree Page Layout

The page layout of a B-Tree page is as follows:

[common-headers from generic_page_header]
[B-tree-specific-headers in btree_page]
(item area in btree_page:
  [item storage part that is growing forwards]
  [(contiguous) free area]
  [item storage part that is growing backwards]
 )

The first item contains the fence keys and foster key, if any: [low-fence-key data (including prefix) + high-fence-key data (without prefix) + chain-fence-high-key data (complete string; chain-fence-high doesn't share prefix!)]. The other items contain the B-tree page's records, one each. These locations are called slots; slot 0 corresponds to item 1 and so on.

B-Tree Slot Layout

We use poor-man's normalized key to speed up searches. Each slot has a field, _poor, that holds the first few bytes of that slot's key as an unsigned integer (poor_man_key) so that comparison with most slot keys can be done without going to the key itself, avoiding L1 cache misses. The whole point of poor_man_key is avoiding cache misses!

NOTE So far, poor-man's normalied key is 2 byte integer (uint16_t) and the corresponding bytes are NOT eliminated from the key string in the record. This is to speed up the retrieval of the (truncated) complete key at the cost of an additional 2 bytes to store it. I admit this is arguable, but deserilizing the first part everytime (it's likely little-endian, so we need to flip it) will slow down retrieval.

Also associated with each slot is a ghost bit (is this record a ghost record?), a variable-size data portion used to hold the record details (i.e., key and element if a leaf node), and in the case of interior nodes, a child pointer.

Record Layout

Internally, record data is stored in the item variable-size data part as follows:

(If the page is leaf page)

key length (uint16_t) AFTER prefix truncation
key + element (contiguous char[]) AFTER prefix truncation NOTE: element length can be calculated from item length and key length (element length = item length - key length - sizeof(key length)).

(If the page is interior node page)

key AFTER prefix truncation NOTE: key-AFTER-prefix-truncation length here is simply the item length.

Opaque pointers:

Default is to return page ID.
When a page is swizzled though we can avoid hash table lookup to map page ID to frame ID by using frame ID directly. Opaque pointers serve this purpose by hiding from the user whether a pointer is a frame ID or page ID.

Member Typedef Documentation

§ key_length_t

typedef uint16_t btree_page_h::key_length_t

private

A field to hold a B-tree key length.

§ pack_scratch_t

typedef key_length_t btree_page_h::pack_scratch_t

private

type of scratch space needed by _pack_leaf_record

§ poor_man_key

typedef uint16_t btree_page_h::poor_man_key

private

Poor man's normalized key type.

To speed up comparison this should be an integer type, not char[].

Member Enumeration Documentation

§ anonymous enum

anonymous enum

private

Enumerator
data_sz
hdr_sz

§ _internal

enum btree_page_h::_internal

private

Enumerator
max_key_length	Maximum key length allows in B-tree pages.

Constructor & Destructor Documentation

§ btree_page_h() [1/2]

btree_page_h::btree_page_h ( )

inline

§ btree_page_h() [2/2]

btree_page_h::btree_page_h ( const btree_page_h & p )

inline

§ ~btree_page_h()

btree_page_h::~btree_page_h ( )

inline

Member Function Documentation

§ _check_space_for_insert()

bool btree_page_h::_check_space_for_insert ( size_t data_length )

private

Returns if there is enough free space to accomodate the given item.

Returns: true if there is free space

§ _compare_key_noprefix()

int btree_page_h::_compare_key_noprefix	(	slotid_t	slot,
		const void *	key_noprefix,
		size_t	key_len
	)		const

inlineprivate

returns compare(specified-key, key_noprefix)

§ _compare_slot_with_key()

int btree_page_h::_compare_slot_with_key	(	int	slot,
		const void *	key_noprefix,
		size_t	key_len,
		poor_man_key	poor
	)		const

inlineprivate

compare slot slot's key with given key (as key_noprefix,key_len,poor tuple) result <0 if slot's key is before given key

§ _element_offset()

size_t btree_page_h::_element_offset ( int slot ) const

inlineprivate

Calculate offset within slot's variable-sized data to its element data. All data from that point onwards makes up the element data.

Precondition: we are a leaf node

§ _extract_poor_man_key() [1/3]

btree_page_h::poor_man_key btree_page_h::_extract_poor_man_key	(	const void *	trunc_key,
		size_t	trunc_key_len
	)		const

inlineprivate

Returns the value of poor-man's normalized key for the given key string WITHOUT prefix.

§ _extract_poor_man_key() [2/3]

btree_page_h::poor_man_key btree_page_h::_extract_poor_man_key ( const cvec_t & trunc_key ) const

inlineprivate

Returns the value of poor-man's normalized key for the given key string WITHOUT prefix.

§ _extract_poor_man_key() [3/3]

btree_page_h::poor_man_key btree_page_h::_extract_poor_man_key	(	const void *	key_with_prefix,
		size_t	key_len_with_prefix,
		size_t	prefix_len
	)		const

inlineprivate

Returns the value of poor-man's normalized key for the given key string WITH prefix.

§ _init()

void btree_page_h::_init	(	lsn_t	lsn,
		PageID	page_id,
		StoreID	store,
		PageID	root_pid,
		PageID	pid0,
		lsn_t	pid0_emlsn,
		PageID	foster_pid,
		lsn_t	foster_emlsn,
		int16_t	btree_level,
		const w_keystr_t &	low,
		const w_keystr_t &	high,
		const w_keystr_t &	chain_fence_high,
		const bool	ghost
	)

private

Initialize the whole image of this page as an empty page.

§ _is_consistent_keyorder()

bool btree_page_h::_is_consistent_keyorder ( ) const

private

internal method used from is_consistent() to check keyorder correctness.

§ _is_consistent_poormankey()

bool btree_page_h::_is_consistent_poormankey ( ) const

private

checks if the poor-man's normalized keys are valid.

§ _is_enough_spacious_ghost()

bool btree_page_h::_is_enough_spacious_ghost	(	const w_keystr_t &	key,
		slotid_t	slot,
		const cvec_t &	el
	)

Tell if the slot is a ghost record and enough spacious to store the given key/data.

§ _leaf_key_noprefix()

const char * btree_page_h::_leaf_key_noprefix	(	slotid_t	slot,
		size_t &	len
	)		const

inlineprivate

Retrieves the key WITHOUT prefix of specified slot in a leaf

Precondition: we are a leaf node

§ _node_key_noprefix()

const char * btree_page_h::_node_key_noprefix	(	slotid_t	slot,
		size_t &	len
	)		const

inlineprivate

Retrieves the key WITHOUT prefix of specified slot in an interior node

Precondition: we are an interior node

§ _pack_fence_rec()

int btree_page_h::_pack_fence_rec	(	cvec_t &	out,
		const w_keystr_t &	low,
		const w_keystr_t &	high,
		const w_keystr_t &	chain,
		int	new_prefix_len
	)		const

inlineprivate

Pack a B-tree page's fence and foster key information into out, suitable for use with insert_item.

All input keys are uncompressed. During packing, prefix elimination is used. The prefix length to truncate is new_prefix_len if non-negative; otherwise, the prefix length to use is computed as the maximum number of common prefix bytes of the low and high fence keys. The prefix length used is returned either way.

The caller is responsible for ensuring that btree_fence_low_length, btree_fence_high_length, btree_chain_fence_high_length are set to the lengths of the corresponding keys and that btree_prefix_length is set to the returned prefix length.

§ _pack_leaf_record()

void btree_page_h::_pack_leaf_record	(	cvec_t &	out,
		pack_scratch_t &	out_scratch,
		const cvec_t &	trunc_key,
		const char *	element,
		size_t	element_len
	)		const

inlineprivate

Pack a leaf record's information into out, suitable for use with insert_item.

trunc_key is the record's key (including its w_keystr_t sign byte) without its prefix; element is the record's associated value.

out_scratch is a scratch work area that the caller must provide; it must remain in scope in order for out to be used (i.e., out will point to part(s) of out_scratch).

§ _pack_leaf_record_prefix()

void btree_page_h::_pack_leaf_record_prefix	(	cvec_t &	out,
		pack_scratch_t &	out_scratch,
		const cvec_t &	trunc_key
	)		const

inlineprivate

Pack a leaf record's key information only into out, suitable for use with insert_item with variable-size–data length computed by _predict_leaf_data_length using in addition the expected element length. (This is used by reserve_ghost to set only the key information leaving reserved space for the future element.)

trunc_key is the record's key (including its w_keystr_t sign byte) without its prefix.

out_scratch is a scratch work area that the caller must provide; it must remain in scope in order for out to be used (i.e., out will point to part(s) of out_scratch).

§ _pack_node_record()

void btree_page_h::_pack_node_record	(	cvec_t &	out,
		const cvec_t &	trunc_key,
		const lsn_t &	emlsn
	)		const

inlineprivate

Pack a node record's information into out, suitable for use with insert_item.

trunc_key is the record's key (including its w_keystr_t sign byte) without its prefix.

emlsn is the expected minimum LSN for the pointed child page. Be VERY careful because both data in trunk_key and emlsn are stored as references. You must keep the original variables until the resulting cvec_t gets out of scope.

§ _poor()

btree_page_h::poor_man_key btree_page_h::_poor ( int slot ) const

inlineprivate

Return poor man's key data for given slot.

§ _predict_leaf_data_length()

size_t btree_page_h::_predict_leaf_data_length	(	int	trunc_key_length,
		int	element_length
	)		const

inlineprivate

Compute needed length of variable-size data to store a leaf record with the given truncated key and element lengths.

§ _steal_records()

void btree_page_h::_steal_records	(	btree_page_h *	steal_src,
		int	steal_from,
		int	steal_to,
		const bool	full_logging
	)

Steal records from steal_src. Called by format_steal.

§ _update_btree_consecutive_skewed_insertions()

void btree_page_h::_update_btree_consecutive_skewed_insertions ( slotid_t slot )

private

Given the place to insert, update btree_consecutive_skewed_insertions.

§ accept_empty_child()

void btree_page_h::accept_empty_child	(	lsn_t	new_lsn,
		PageID	new_page_id,
		const bool	f_redo
	)

Parameters

[in]	new_lsn	LSN of the operation that creates the foster-child page.
[in]	new_page_id	Page ID of the new page.
[in]	f_redo	true if caller is from redo logic.

See also: btree_impl::_sx_norec_alloc(); btree_norec_alloc_log::redo

Precondition: in SSX (thus REDO-only. no worry for compensation log); latch_mode() == EX

§ btree_root()

PageID btree_page_h::btree_root ( ) const

inline

§ calculate_prefix_length()

int16_t btree_page_h::calculate_prefix_length	(	int16_t	existing_prefix_len,
		w_keystr_t	low_key,
		w_keystr_t	high_key
	)

§ check_chance_for_norecord_split()

bool btree_page_h::check_chance_for_norecord_split ( const w_keystr_t & key_to_insert ) const

Returns if whether we can do norecord insert now.

§ check_space_for_insert_leaf() [1/2]

bool btree_page_h::check_space_for_insert_leaf	(	const w_keystr_t &	trunc_key,
		const cvec_t &	el
	)

Returns if there is enough free space to accomodate the given new record.

Returns: true if there is free space

§ check_space_for_insert_leaf() [2/2]

bool btree_page_h::check_space_for_insert_leaf	(	size_t	trunc_key_length,
		size_t	element_length
	)

§ check_space_for_insert_node()

bool btree_page_h::check_space_for_insert_node ( const w_keystr_t & key )

for intermediate node (no element).

§ child()

PageID btree_page_h::child ( slotid_t slot ) const

Return the (non-opaque) child pointer of record in slot.

§ child_opaqueptr()

PageID btree_page_h::child_opaqueptr ( slotid_t slot ) const

inline

Return the opaque child pointer of record in slot.

§ compare_with_chain_fence_high() [1/2]

int btree_page_h::compare_with_chain_fence_high ( const w_keystr_t & key ) const

inline

Return value : 0 if equal. : <0 if key < fence-high. : >0 if key > fence-high.

§ compare_with_chain_fence_high() [2/2]

int btree_page_h::compare_with_chain_fence_high	(	const char *	key,
		size_t	key_len
	)		const

inline

overload for char*.

§ compare_with_fence_high() [1/2]

int btree_page_h::compare_with_fence_high ( const w_keystr_t & key ) const

inline

Return value : 0 if equal. : <0 if key < fence-high. : >0 if key > fence-high.

§ compare_with_fence_high() [2/2]

int btree_page_h::compare_with_fence_high	(	const char *	key,
		size_t	key_len
	)		const

inline

overload for char*.

§ compare_with_fence_high_noprefix()

int btree_page_h::compare_with_fence_high_noprefix	(	const char *	key,
		size_t	key_len
	)		const

inline

used when the prefix part is already checked key/key_len must be WITHOUT prefix.

§ compare_with_fence_low() [1/2]

int btree_page_h::compare_with_fence_low ( const w_keystr_t & key ) const

inline

Return value : 0 if equal. : <0 if key < fence-low. : >0 if key > fence-low.

§ compare_with_fence_low() [2/2]

int btree_page_h::compare_with_fence_low	(	const char *	key,
		size_t	key_len
	)		const

inline

overload for char*.

§ compare_with_fence_low_noprefix()

int btree_page_h::compare_with_fence_low_noprefix	(	const char *	key,
		size_t	key_len
	)		const

inline

used when the prefix part is already checked key/key_len must be WITHOUT prefix.

§ compress()

rc_t btree_page_h::compress	(	const w_keystr_t &	low,
		const w_keystr_t &	high,
		const w_keystr_t &	chain,
		bool	redo = `false`
	)

Compress page by trying to expand the prefix and truncate keys even further.

§ copy_chain_fence_high_key()

void btree_page_h::copy_chain_fence_high_key ( w_keystr_t & buffer ) const

inline

Constructs w_keystr_t object containing the low-fence key of this page.

§ copy_element()

bool btree_page_h::copy_element	(	int	slot,
		char *	out_buffer,
		smsize_t &	len,
		bool &	ghost
	)		const

Attempt to copy element of given record to provided buffer (out_buffer[0..len-1]). Returns false iff failed due to insufficient buffer size.

Sets len to actual element size in all cases. Also returns ghost status of given record.

Precondition: we are a leaf page

§ copy_fence_high_key()

void btree_page_h::copy_fence_high_key ( w_keystr_t & buffer ) const

inline

Constructs w_keystr_t object containing the low-fence key of this page.

§ copy_fence_low_key()

void btree_page_h::copy_fence_low_key ( w_keystr_t & buffer ) const

inline

Constructs w_keystr_t object containing the low-fence key of this page.

§ copy_records()

rc_t btree_page_h::copy_records	(	const int	rec_count,
		char *	data_buffer,
		smsize_t &	len
	)

§ defrag()

rc_t btree_page_h::defrag ( const bool full_logging_redo = false )

Defrags this 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.

§ delete_range()

void btree_page_h::delete_range	(	int	from,
		int	to
	)

§ element()

const char * btree_page_h::element	(	int	slot,
		smsize_t &	len,
		bool &	ghost
	)		const

Return pointer to, length of element of given record. Also returns ghost status of given record.

Precondition: we are a leaf page

§ fence_contains()

bool btree_page_h::fence_contains ( const w_keystr_t & key ) const

inline

Returns if the given key can exist in the range specified by fence keys, which is low-fence <= key < high-fence.

§ format_foster_child()

rc_t btree_page_h::format_foster_child	(	btree_page_h &	parent,
		const PageID &	new_page_id,
		const w_keystr_t &	triggering_key,
		w_keystr_t &	split_key,
		int &	move_count
	)

Initialize the page as a foster child of the given parent.

Moves records from the given (foster) parent page based on the given split-triggering key. Initializes the fence keys accordingly.

Author: Caetano Sauer

§ format_steal()

rc_t btree_page_h::format_steal	(	lsn_t	new_lsn,
		const PageID &	pid,
		StoreID	store,
		PageID	root,
		int	level,
		PageID	pid0,
		lsn_t	pid0_emlsn,
		PageID	foster,
		lsn_t	foster_emlsn,
		const w_keystr_t &	fence_low,
		const w_keystr_t &	fence_high,
		const w_keystr_t &	chain_fence_high,
		bool	log_it = `true`,
		btree_page_h *	steal_src1 = `nullptr`,
		int	steal_from1 = `0`,
		int	steal_to1 = `0`,
		btree_page_h *	steal_src2 = `nullptr`,
		int	steal_from2 = `0`,
		int	steal_to2 = `0`,
		bool	steal_src2_pid0 = `false`,
		const bool	full_logging = `false`,
		const bool	log_src_1 = `false`,
		const bool	ghost = `false`
	)

Initializes the associated page, stealing records from other pages as specified.

This sets all headers, fence/prefix keys, and initial records altogether. Steals records from steal_src1 if non-null. Then steal records from steal_src2 if non-null (this is used only when merging). If steal_src2_pid0 is true, it also steals src2's pid0 with low-fence key.

Parameters

[in]	new_lsn	LSN of the operation that creates this page.
[in]	pid	Page ID of the new page; this must match pid used to fix this page if a buffer pool-manage page.
[in]	root	Page ID of the root page of the B-tree this page belongs to.
[in]	level	Level of the new page.
[in]	pid0	New pid0 value
[in]	foster	Page ID of the (if exists) foster-child of the parent.
[in]	fence_low	The fence low key of the new page.
[in]	fence_high	The fence high key of the new page.
[in]	chain_fence_high	Highest key in the foster chain.
[in]	log_it	Should we log this change? ...

§ get_chain_fence_high_key()

const char * btree_page_h::get_chain_fence_high_key ( ) const

inline

Returns the high fence key of foster chain.

§ get_chain_fence_high_length()

int16_t btree_page_h::get_chain_fence_high_length ( ) const

inline

Returns the length of high fence key of foster chain.

§ get_emlsn_general()

const lsn_t & btree_page_h::get_emlsn_general ( general_recordid_t pos ) const

inline

Returns the Expected Child LSN of pid0, foster-child, or real child.

§ get_fence_high_key_noprefix()

const char * btree_page_h::get_fence_high_key_noprefix ( ) const

inline

Returns the high fence key (without prefix), which is larger than all entries in this page and its descendants. NOTE we don't provide get_fence_high_key() with prefix because the page eliminates prefix from fence-high.

§ get_fence_high_length()

int16_t btree_page_h::get_fence_high_length ( ) const

inline

Returns the length of high fence key with prefix.

§ get_fence_high_length_noprefix()

int16_t btree_page_h::get_fence_high_length_noprefix ( ) const

inline

Returns the length of high fence key without prefix.

§ get_fence_low_key()

const char * btree_page_h::get_fence_low_key ( ) const

inline

Returns the low fence key, which is same OR smaller than all entries in this page and its descendants.

§ get_fence_low_length()

int16_t btree_page_h::get_fence_low_length ( ) const

inline

Returns the length of low fence key.

§ get_foster()

PageID btree_page_h::get_foster ( ) const

Returns ID of B-link page (0 if not linked).

§ get_foster_opaqueptr()

PageID btree_page_h::get_foster_opaqueptr ( ) const

inline

Returns opaque pointer of B-link page (0 if not linked).

§ get_key()

void btree_page_h::get_key	(	slotid_t	slot,
		w_keystr_t &	key
	)		const

Retrieves key from given record #.

§ get_prefix_key()

const char * btree_page_h::get_prefix_key ( ) const

inline

Returns the prefix which is removed from all entries in this page.

§ get_prefix_length()

int16_t btree_page_h::get_prefix_length ( ) const

inline

Returns the length of prefix key (0 means no prefix compression).

§ get_rec_space()

size_t btree_page_h::get_rec_space ( int slot ) const

inline

Returns physical space used by the record currently in the given slot (including padding and other overhead due to that slot being occupied).

§ init_fence_keys()

rc_t btree_page_h::init_fence_keys	(	const bool	set_low,
		const w_keystr_t &	low,
		const bool	set_high,
		const w_keystr_t &	high,
		const bool	set_chain,
		const w_keystr_t &	chain_fence_high,
		const bool	set_pid0,
		const PageID	new_pid0,
		const bool	set_emlsn,
		const lsn_t	new_pid0_emlsn,
		const bool	set_foster,
		const PageID	foster_pid0,
		const bool	set_foster_emlsn,
		const lsn_t	foster_emlsn,
		const int	remove_count = `0`
	)

§ insert_node()

rc_t btree_page_h::insert_node	(	const w_keystr_t &	key,
		slotid_t	slot,
		PageID	child,
		const lsn_t &	child_emlsn
	)

Insert a new entry at "slot". This is used only for non-leaf pages. For leaf pages, always use replace_ghost() and reserve_ghost().

Parameters

[in]	child	child pointer to add
[in]	child_emlsn	Expected child LSN of the pointed page

§ insert_nonghost()

void btree_page_h::insert_nonghost	(	const w_keystr_t &	key,
		const cvec_t &	elem
	)

Creates a non-ghost record with the given key and data. If the record already exists as a ghost, we reuse it. This is logically a combination of reserve_ghost() and replace_ghost(), but this does the two in one-go. This function itself does NOT log, so the caller is responsible for it.

Parameters

[in]	key	inserted key
[in]	elem	record data

Precondition: is_leaf(); the page has enough space to insert the record. The caller must make sure this is the case.

§ insert_records_dest_redo()

rc_t btree_page_h::insert_records_dest_redo	(	const int16_t	prefix_len,
		const int32_t	move_count,
		const int16_t	record_data_len,
		const char *	record_data
	)

§ int_stats()

rc_t btree_page_h::int_stats ( btree_int_stats_t & btree_int )

stats for interior nodes.

§ is_consistent()

bool btree_page_h::is_consistent	(	bool	check_keyorder = `false`,
		bool	check_space = `false`
	)		const

Checks integrity of this page. This function does NOT check integrity across multiple pages. For that purpose, use btree_m::verify_tree(). If the two arguments are both false (which is default), this function should be very efficient.

Parameters

[in]	check_keyorder	whether to check the sortedness and uniqueness of the keys in this page. setting this to true makes this function expensive.
[in]	check_space	whether to check any overlaps of records and integrity of space offset. setting this to true makes this function expensive.

Returns: true if this page is in a consistent state

§ is_fence_high_supremum()

bool btree_page_h::is_fence_high_supremum ( ) const

inline

Returns if the high-fence key is supremum.

§ is_fence_low_infimum()

bool btree_page_h::is_fence_low_infimum ( ) const

inline

Returns if the low-fence key is infimum.

§ is_ghost()

bool btree_page_h::is_ghost ( slotid_t slot ) const

inline

Returns if the specified record is a ghost record.

§ is_insertion_extremely_skewed_right()

bool btree_page_h::is_insertion_extremely_skewed_right ( ) const

inline

§ is_insertion_skewed_left()

bool btree_page_h::is_insertion_skewed_left ( ) const

inline

§ is_insertion_skewed_right()

bool btree_page_h::is_insertion_skewed_right ( ) const

inline

§ is_leaf()

bool btree_page_h::is_leaf ( ) const

inline

Is associated page a leaf?

§ is_leaf_parent()

bool btree_page_h::is_leaf_parent ( ) const

inline

return true if this node is the lowest interior node, * i.e., the parent of a leaf. Used to tell how we should * latch a child page : EX or SH *

§ is_node()

bool btree_page_h::is_node ( ) const

inline

Returns if this page is NOT a leaf.

§ leaf_stats()

rc_t btree_page_h::leaf_stats ( btree_lf_stats_t & btree_lf )

stats for leaf nodes.

§ level()

int btree_page_h::level ( ) const

inline

Returns 1 if leaf, >1 if non-leaf.

§ mark_ghost()

void btree_page_h::mark_ghost ( slotid_t slot )

Mark the given slot to be a ghost record. If the record is already a ghost, does nothing. This is used by delete and insert (UNDO). This function itself does NOT log, so the caller is responsible for it.

See also: defrag()

§ nghosts()

int btree_page_h::nghosts ( ) const

inline

Returns the number of ghosts records in this page.

§ norecord_split()

rc_t btree_page_h::norecord_split	(	PageID	foster,
		lsn_t	foster_emlsn,
		const w_keystr_t &	fence_high,
		const w_keystr_t &	chain_fence_high
	)

Called when we did a split from this page but didn't move any record to new page. This method can't be undone. Use this only for REDO-only system transactions.

§ nrecs()

int btree_page_h::nrecs ( ) const

inline

Returns the number of records in this page.

§ operator=()

btree_page_h& btree_page_h::operator= ( btree_page_h & p )

inline

§ overwrite_el_nolog()

void btree_page_h::overwrite_el_nolog	(	slotid_t	slot,
		smsize_t	offset,
		const char *	new_el,
		smsize_t	elen
	)

Similar to replace_el_nolog(), but this overwrites specific part of the element and never changes the size of record, so it's simpler, faster and can't throw error.

§ page()

btree_page* btree_page_h::page ( ) const

inlineprivate

§ page_pointer_address()

PageID * btree_page_h::page_pointer_address ( int offset )

inline

Returns a pointer to given page pointer (e.g., PageID).

Offset may be -2 for leaf nodes or [-2,nrecs()-1] for internal nodes. It denotes:

-2: the foster pointer -1: pid0 0..nrec()-1: the child pointer of the record in the corresponding slot

The page pointer will be at a 4-byte aligned address and opaque.

(This method is used to implement swizzling of page pointers atomically.)

§ pid0()

PageID btree_page_h::pid0 ( ) const

Returns left-most ptr (used only in non-leaf nodes).

§ pid0_opaqueptr()

PageID btree_page_h::pid0_opaqueptr ( ) const

inline

Returns left-most opaque pointer (used only in non-leaf nodes).

§ print()

void btree_page_h::print ( bool print_elem = false )

Debugs out the contents of this page.

§ recalculate_fence_for_split()

w_keystr_t btree_page_h::recalculate_fence_for_split ( slotid_t right_begins_from ) const

For recovering the separator key from boundary place.

See also: suggest_fence_for_split().

§ remove_shift_nolog()

rc_t btree_page_h::remove_shift_nolog ( slotid_t slot )

Remove the slot and up-shift slots after the hole to fill it up.

Parameters

slot	the slot to remove.

§ replace_el_nolog()

rc_t btree_page_h::replace_el_nolog	(	slotid_t	slot,
		const cvec_t &	elem
	)

Replaces the given slot with the new data. key is not changed. If we need to expand the record and the page doesn't have enough space, eRECWONTFIT is thrown.

§ replace_fence_rec_nolog_may_defrag()

rc_t btree_page_h::replace_fence_rec_nolog_may_defrag	(	const w_keystr_t &	low,
		const w_keystr_t &	high,
		const w_keystr_t &	chain,
		int	new_prefix_length = `-1`
	)

Replaces the special fence record with the given new data, expanding the slot length if needed.

This method also updates fence_low/high/chain-high_length. Also, this method may defrag the page to squeeze out space for the fence keys if needed (returns eRECWONTFIT if it still doesn't fit).

§ replace_fence_rec_nolog_no_defrag()

rc_t btree_page_h::replace_fence_rec_nolog_no_defrag	(	const w_keystr_t &	low,
		const w_keystr_t &	high,
		const w_keystr_t &	chain,
		int	new_prefix_length
	)

See also: replace_fence_rec_nolog_may_defrag().

§ replace_ghost()

rc_t btree_page_h::replace_ghost	(	const w_keystr_t &	key,
		const cvec_t &	elem,
		bool	redo = `false`
	)

Replace an existing ghost record to insert the given tuple. This assumes the ghost record is enough spacious.

Parameters

[in]	key	inserted key
[in]	elem	record data

§ reserve_ghost() [1/2]

void btree_page_h::reserve_ghost	(	const w_keystr_t &	key,
		size_t	element_length
	)

inline

Creates a dummy ghost record with the given key and element length as a preparation for subsequent insertion. This is used by insertion (its nested system transaction). This function itself does NOT log, so the caller is responsible for it.

§ reserve_ghost() [2/2]

void btree_page_h::reserve_ghost	(	const char *	key_raw,
		size_t	key_raw_len,
		size_t	element_length
	)

§ root()

PageID btree_page_h::root ( ) const

inline

Returns root page; used for recovery.

§ search() [1/2]

void btree_page_h::search	(	const w_keystr_t &	key,
		bool &	found_key,
		slotid_t &	return_slot
	)		const

inline

Search for given key in this B-tree page. Stores in found_key the key found status and in return_slot the slot where the key was found or (if not found) the slot where the key should go if inserted. Note in the latter case that return_slot may be nrecs().

§ search() [2/2]

void btree_page_h::search	(	const char *	key_raw,
		size_t	key_raw_len,
		bool &	found_key,
		slotid_t &	return_slot
	)		const

Search for given key in this B-tree page. Stores in found_key the key found status and in return_slot the slot where the key was found or (if not found) the slot where the key should go if inserted. Note in the latter case that return_slot may be nrecs().

§ search_node()

void btree_page_h::search_node	(	const w_keystr_t &	key,
		slotid_t &	return_slot
	)		const

Search for given key in this interior node, determining which child pointer should be taken to continue searching down the B-tree.

Stores in return_slot the slot whose child pointer should be followed, with -1 denoting that the pid0 child pointer should be followed.

Note: keys in interior nodes are separator keys. Like fence keys, a separator key is exclusive for left and inclusive for right. For example, a separator key "AB" sends "AA" to left, "AAZ" to left, "AB" to right, "ABA" to right, and "AC" to right.

Precondition: this is an interior node

§ set_foster_child()

bool btree_page_h::set_foster_child	(	PageID	foster_child_pid,
		const w_keystr_t &	new_fence_high,
		const w_keystr_t &	child_fence_chain
	)

Sets the given page ID as foster child of this page.

Adjusts not only the foster child pointer, but also the high fence key – which must change to the separator key that caused the split – and the chain fence key, which must be copied from the foster child.

Author: Caetano Sauer

§ suggest_fence_for_split()

void btree_page_h::suggest_fence_for_split	(	w_keystr_t &	mid,
		slotid_t &	right_begins_from,
		const w_keystr_t &	triggering_key
	)		const

Suggests a new fence key, assuming this page is being split.

The new "mid" fence key will be the new left sibling's high fence key and also the right sibling's low fence key after split. right_begins_from returns the slot id from which (including it) the new right sibling steal the entires.

Parameters

[out]	mid	suggested fence key in the middle
[out]	right_begins_from	slot id from which (including it) the new right sibling steal the entires
[in]	triggering_key	the key to be inserted after this split. used to determine split policy.

§ unmark_ghost()

void btree_page_h::unmark_ghost ( slotid_t slot )

Un-Mark the given slot to be a regular record. If the record is already a non-ghost, does nothing. This is only used by delete (UNDO). This function itself does NOT log, so the caller is responsible for it.

§ usable_space()

smsize_t btree_page_h::usable_space ( ) const

inline

§ used_space()

smsize_t btree_page_h::used_space ( ) const

inline

Friends And Related Function Documentation

§ btree_ghost_mark_log

friend class btree_ghost_mark_log

friend

§ btree_ghost_reclaim_log

friend class btree_ghost_reclaim_log

friend

§ btree_ghost_t

template<class T >

friend class btree_ghost_t

friend

§ btree_impl

friend class btree_impl

friend

§ btree_split_log

friend class btree_split_log

friend

§ operator<<

std::ostream& operator<<	(	std::ostream &	os,
		btree_page_h &	b
	)

friend

§ page_img_format_t

template<class T >

friend class page_img_format_t

friend

Member Data Documentation

§ max_entry_size

smsize_t btree_page_h::max_entry_size

static

Initial value:

=
        
        (btree_page::data_sz - 3 * btree_page::max_item_overhead - 2 * sizeof(key_length_t)) / 5 - 1

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

src/sm/btree_page_h.h
src/sm/btree_page_h.cpp

Classes

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Friends

Additional Inherited Members

Detailed Description

Fence Keys and B-link Tree

B-Tree Page Layout

B-Tree Slot Layout

Record Layout

Member Typedef Documentation

§ key_length_t

§ pack_scratch_t

§ poor_man_key

Member Enumeration Documentation

§ anonymous enum

§ _internal

Constructor & Destructor Documentation

§ btree_page_h() [1/2]

§ btree_page_h() [2/2]

§ ~btree_page_h()

Member Function Documentation

§ _check_space_for_insert()

§ _compare_key_noprefix()

§ _compare_slot_with_key()

§ _element_offset()

§ _extract_poor_man_key() [1/3]

§ _extract_poor_man_key() [2/3]

§ _extract_poor_man_key() [3/3]

§ _init()

§ _is_consistent_keyorder()

§ _is_consistent_poormankey()

§ _is_enough_spacious_ghost()

§ _leaf_key_noprefix()

§ _node_key_noprefix()

§ _pack_fence_rec()

§ _pack_leaf_record()

§ _pack_leaf_record_prefix()

§ _pack_node_record()

§ _poor()

§ _predict_leaf_data_length()

§ _steal_records()

§ _update_btree_consecutive_skewed_insertions()

§ accept_empty_child()

§ btree_root()

§ calculate_prefix_length()

§ check_chance_for_norecord_split()

§ check_space_for_insert_leaf() [1/2]

§ check_space_for_insert_leaf() [2/2]

§ check_space_for_insert_node()

§ child()

§ child_opaqueptr()

§ compare_with_chain_fence_high() [1/2]

§ compare_with_chain_fence_high() [2/2]

§ compare_with_fence_high() [1/2]

§ compare_with_fence_high() [2/2]

§ compare_with_fence_high_noprefix()

§ compare_with_fence_low() [1/2]

§ compare_with_fence_low() [2/2]

§ compare_with_fence_low_noprefix()

§ compress()

§ copy_chain_fence_high_key()

§ copy_element()

§ copy_fence_high_key()

§ copy_fence_low_key()

§ copy_records()

§ defrag()

§ delete_range()

§ element()

§ fence_contains()

§ format_foster_child()

§ format_steal()

§ get_chain_fence_high_key()

§ get_chain_fence_high_length()

§ get_emlsn_general()

§ get_fence_high_key_noprefix()

§ get_fence_high_length()

§ get_fence_high_length_noprefix()