B+-Tree Indexes
[Storage Structures]

Collaboration diagram for B+-Tree Indexes:

---

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. Keys may be composed of any of the basic C-language types (integer, unsigned, floating-point of several sizes) or variable-length character strings (wide characters are not supported).

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 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).

A variety of locking protocols is supported:

• none : acquire no locks on the {key,value} pairs in the index, although an intention lock might be acquired on the index.
• kvl : key-value locking See [MOH1]. The key or key-value pair is hashed into a 4-byte value and used with the given store id to make a lock id.
• im : index-management locking See [MOH1]. The "value" portion of the key-value lock is taken to be a record id, which is used for the lock id.
• modified kvl : an ad-hoc protocol used by the Paradise project. See the scan_index_i constructor. As with index-management locking, the "value" portion of the key-value lock is taken to be a record id, which is used for the lock id.
• file : full-index locking.

Key Types

A B+-Tree index key has a type determined when the index is created. All keys are stored in lexicographic format based on an interpretation of the key determined by the key description given when the index is created. Lookups on the B+-Tree then involve a single byte-by-byte comparison of two byte-strings, each composed of its concatenated sub-keys.

The key description is a null-terminated string as follows:

     <key_decription>     ::=  <fixed_len_part>*  <variable_len_part>  |
                               <fixed_len_part>+ 
     <fixed_len_part>     ::=  <type> <len> 
     <variable_len_part>  ::=  <type> '*' <len>
     <type>               ::=  'i' | 'u' | 'f' | 'b' | 'I' | 'U' | 'F' | 'B'
     <len>                ::=   [1-9][0-9]*
     

Thus, a key may have any number of fixed-length parts followed by at most one variable-length part.

The fixed-length parts (if present) consist of a type and a length.

The variable-length part (if present) consists of a type and a length separated by an asterisk, which is what distinguishes a variable-length from a fixed-length part.

Types and permissible lengths are:

• integer (1,2,4,8)
• unsigned (1,2,4,8)
• floating (4,8)
• uninterpreted byte (any length greater than zero)

A capital letter indicates that the key part may be compressed. Only prefix compression is implemented, so it makes sense to compress if the first part of the key is compressible.

Examples:

• "B40u4u2u2" : 40-byte character string followed by a 4-byte integer, a 2-byte integer and a 2-byte integer, such as one might use for name.year.mo.day. The character string is prefix-compressed.
• "f8" : an 8-byte floating-point number (double)
• "I8B*1000" : An 8-byte integer followed by an uninterpreted string of up to 1000 bytes, all prefix-compressed.

Note:

Wide characters are not supported.

This key descriptor is stored in the sm_store_info_t, which is stored on the volume and is available with the method ss_m::get_store_info. Keys are stored in lexicographic format. The storage manager knows how to convert all the key types listed above. When duplicates are permitted, the index assumes that the elements are in lexicographic order when searching for a <key,element> pair.

Bulk Loading

Bulk-loading of all index types is supported. See Bulk-Loading Indexes.

Functions
static rc_t	ss_m::create_index (vid_t vid, ndx_t ntype, store_property_t property, const char *key_desc, concurrency_t cc, stid_t &stid)
	Create a B+-Tree index.
static rc_t	ss_m::create_index (vid_t vid, ndx_t ntype, store_property_t property, const char *key_desc, stid_t &stid)
	Create a B+-Tree or R*-Tree index.
static rc_t	ss_m::destroy_index (const stid_t &iid)
	Destroy a B+-Tree index.
static rc_t	ss_m::create_assoc (stid_t stid, const vec_t &key, const vec_t &el)
	Create an entry in a B+-Tree index.
static rc_t	ss_m::destroy_assoc (stid_t stid, const vec_t &key, const vec_t &el)
	Remove an entry from a B+-Tree index.
static rc_t	ss_m::destroy_all_assoc (stid_t stid, const vec_t &key, int &num_removed)
	Destroy all entries associated with a key in a B+-Tree index.
static rc_t	ss_m::find_assoc (stid_t stid, const vec_t &key, void *el, smsize_t &elen, bool &found)
	Find an entry associated with a key in a B+-Tree index.

---

Function Documentation

static rc_t ss_m::create_index	(	vid_t	vid,
		ndx_t	ntype,
		store_property_t	property,
		const char *	key_desc,
		concurrency_t	cc,
		stid_t &	stid
	)			[static, inherited]

Create a B+-Tree index.

Parameters:

[in]	vid	Volume on which to create the index.
[in]	ntype	Type of index. Legitimate values are: t_btree : B+-Tree with duplicate keys allowed t_uni_btree : B+-Tree without duplicate keys
[in]	property	Logging level of store. Legitimate values are: t_regular t_load_file t_insert_file See sm_store_property_t for details.
[in]	key_desc	Description of key type. See Key Types for details.
[in]	cc	The locking protocol to use with this index. See smlevel_0::concurrency_t and B+-Tree Indexes.
[out]	stid	New store ID will be returned here.

static rc_t ss_m::create_index	(	vid_t	vid,
		ndx_t	ntype,
		store_property_t	property,
		const char *	key_desc,
		stid_t &	stid
	)			[static, inherited]

Create a B+-Tree or R*-Tree index.

Attention:

For backward compatibility. Will be deprecated later.

static rc_t ss_m::destroy_index

(

const stid_t &

iid

)

[static, inherited]

Destroy a B+-Tree index.

Parameters:

[in]

iid

ID of the index to be destroyed.

static rc_t ss_m::create_assoc	(	stid_t	stid,
		const vec_t &	key,
		const vec_t &	el
	)			[static, inherited]

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 and element vectors must be less than or equal to max_entry_size.

Examples:

create_rec.cpp, log_exceed.cpp, sort_stream.cpp, and vtable_example.cpp.

static rc_t ss_m::destroy_assoc	(	stid_t	stid,
		const vec_t &	key,
		const vec_t &	el
	)			[static, inherited]

Remove an entry from a B+-Tree index.

Parameters:

[in]	stid	ID of the index.
[in]	key	Key of the entry to be removed.
[in]	el	Element (value) of the entry to be removed.

static rc_t ss_m::destroy_all_assoc	(	stid_t	stid,
		const vec_t &	key,
		int &	num_removed
	)			[static, inherited]

Destroy all entries 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]	num_removed	The number of entries removed is returned here.

static rc_t ss_m::find_assoc	(	stid_t	stid,
		const vec_t &	key,
		void *	el,
		smsize_t &	elen,
		bool &	found
	)			[static, inherited]

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.

To locate all entries associated with a non-unique key, you must use scan_index_i, q.v..

Examples:

create_rec.cpp, log_exceed.cpp, sort_stream.cpp, and vtable_example.cpp.

---