This class holds B-tree-specific headers as well as an ordered list of items. More...
#include <btree_page.h>
Classes | |
| struct | item_body |
| struct | item_head |
Public Types | |
| enum | { hdr_sz = sizeof(generic_page_header) + 48, data_sz = sizeof(generic_page) - hdr_sz } |
Public Member Functions | |
| bool | eq (const btree_page_data &) const |
 Public Member Functions inherited from generic_page_header | |
| uint32_t | calculate_checksum () const |
| Calculate the correct value of checksum for this page. More... | |
Protected Types | |
| typedef uint16_t | poor_man_key |
| The type of poor_man_key data. More... | |
Protected Member Functions | |
| void | init_items () |
| void | remove_items (const int item_count, const w_keystr_t &high) |
| int | number_of_items () const |
| int | number_of_ghosts () const |
| return number of current items that are ghosts More... | |
| bool | is_ghost (int item) const |
| is the given item a ghost? More... | |
| void | set_ghost (int item) |
| turn the given item into a ghost item More... | |
| void | unset_ghost (int item) |
| turn the given item into a non-ghost item More... | |
| poor_man_key | item_poor (int item) const |
| return the poor_man_key data for the given item More... | |
| poor_man_key & | item_poor (int item) |
| return a reference to the poor_man_key data for the given item More... | |
| PageID & | item_child (int item) |
| char * | item_data (int item) |
| size_t | item_length (int item) const |
| bool | insert_item (int item, bool ghost, poor_man_key poor, PageID child, size_t data_length) |
| bool | insert_item (int item, bool ghost, poor_man_key poor, PageID child, const cvec_t &data) |
| bool | resize_item (int item, size_t new_length, size_t keep_old) |
| bool | replace_item_data (int item, size_t offset, const cvec_t &new_data) |
| void | delete_item (int item) |
| void | delete_range (int from, int to) |
| void | truncate_all (size_t amount, size_t pos) |
| size_t | item_space (int item) const |
| size_t | predict_item_space (size_t data_length) const |
| size_t | usable_space () const |
| void | compact () |
| compact item space, making all freed space available. More... | |
| char * | unused_part (size_t &length) |
| bool | _items_are_consistent () const |
Protected Attributes | |
| PageID | btree_root |
| PageID | btree_pid0 |
| First child pointer in non-leaf nodes. More... | |
| PageID | btree_foster |
| Foster link page ID (0 if not linked). More... | |
| int16_t | btree_level |
| int16_t | btree_fence_low_length |
| int16_t | btree_fence_high_length |
| int16_t | btree_chain_fence_high_length |
| int16_t | btree_prefix_length |
| int16_t | btree_consecutive_skewed_insertions |
| lsn_t | btree_pid0_emlsn |
| lsn_t | btree_foster_emlsn |
| Protected Attributes inherited from generic_page_header | |
| uint16_t | page_flags |
| Page flags (an OR of page_flag_t's) More... | |
| uint64_t | reserved |
| Reserved for subclass usage. More... | |
Static Protected Attributes | |
| static const size_t | max_item_overhead |
Private Types | |
| enum | { max_heads = data_sz / sizeof(item_head), max_bodies = data_sz / sizeof(item_body), leaf_overhead = sizeof(item_length_t), interior_overhead = sizeof(item_length_t) + sizeof(PageID) } |
| typedef uint16_t | item_index_t |
| typedef uint16_t | item_length_t |
| typedef int16_t | body_offset_t |
Private Member Functions | |
| BOOST_STATIC_ASSERT (sizeof(item_head)==4) | |
| BOOST_STATIC_ASSERT (sizeof(item_body)==8) | |
| BOOST_STATIC_ASSERT (data_sz % sizeof(item_body)==0) | |
| STATIC_LESS_THAN (data_sz, 1<<(sizeof(item_length_t) *8)) | |
| STATIC_LESS_THAN (max_heads, 1<<(sizeof(item_index_t) *8)) | |
| STATIC_LESS_THAN (max_bodies, 1<<(sizeof(body_offset_t) *8 - 1)) | |
| bool | is_leaf () const |
| are we a leaf node? More... | |
| size_t | _item_body_overhead () const |
| add this to data length to get bytes used in item bodies (not counting padding) More... | |
| item_length_t & | _item_body_length (body_offset_t offset) |
| item_length_t | _item_body_length (body_offset_t offset) const |
| body_offset_t | _item_bodies (body_offset_t offset) const |
Static Private Member Functions | |
| static size_t | _item_align (size_t i) |
| align to item_body alignment boundary (integral multiple of item_body's) More... | |
Private Attributes | |
| item_index_t | nitems |
| current number of items More... | |
| item_index_t | nghosts |
| number of current ghost items More... | |
| body_offset_t | first_used_body |
| offset to beginning of used item bodies (# of used item body that is located left-most). More... | |
| uint16_t | padding |
| padding to ensure header size is a multiple of 8 More... | |
| union { | |
| item_head head [max_heads] | |
| item_body body [max_bodies] | |
| }; | |
Friends | |
| std::ostream & | operator<< (std::ostream &, btree_page_data &) |
Additional Inherited Members | |
| Public Attributes inherited from generic_page_header | |
| uint32_t | checksum |
| Stored checksum of this page. More... | |
| PageID | pid |
| ID of this page. More... | |
| lsn_t | lsn |
| LSN (Log Sequence Number) of the last write to this page. More... | |
| StoreID | store |
| ID of the store to which this page belongs (0 if none) More... | |
| uint16_t | tag |
| Page type (a page_tag_t) More... | |
| Static Public Attributes inherited from generic_page_header | |
| static const size_t | page_sz = SM_PAGESIZE |
| Size of all Zero pages. More... | |
Detailed Description
This class holds B-tree-specific headers as well as an ordered list of items.
Each item contains the following fixed-size fields:
- ghost? (1 bit): am I a ghost item?
- poor (2 bytes): leading bytes of an associated key for speeding up search (type poor_man_key)
- child (4 bytes): child page ID; this field is present only in interior nodes
The first two fields are stored so that for nearby items (in the list order) they are likely to be in the same cache line; e.g., item_poor(n) and item_poor(n+1) are likely in the same cache line. Each item also contains a variable-length data field, which can be dynamically resized.
For how these fields are used, including the representations used with the variable-length data field, see the btree_page_h class.
The contents of this class are separated out from btree_page to increase access-control flexibility. Its private members are accessible by only itself while its protected members are accessible to only those classes/members friended by btree_page.
Member Typedef Documentation
§ body_offset_t
|
private |
An offset denoting a particular item body, namely body[abs(<offset>)]. In some cases, the sign bit is used to encode ghostness.
§ item_index_t
|
private |
§ item_length_t
|
private |
§ poor_man_key
|
protected |
The type of poor_man_key data.
Member Enumeration Documentation
§ anonymous enum
| anonymous enum |
§ anonymous enum
|
private |
Member Function Documentation
§ _item_align()
|
inlinestaticprivate |
§ _item_bodies()
|
inlineprivate |
return number of item bodies holding data for the items starting at offset offset
§ _item_body_length() [1/2]
|
inlineprivate |
return reference to current number of bytes used in item bodies (not counting padding) associated with the item starting at offset offset
§ _item_body_length() [2/2]
|
inlineprivate |
return current number of bytes used in item bodies (not counting padding) associated with the item starting at offset offset
§ _item_body_overhead()
|
inlineprivate |
add this to data length to get bytes used in item bodies (not counting padding)
§ _items_are_consistent()
|
protected |
[debugging] are item allocations consistent? E.g., do two item allocations overlap? This should always be true.
§ BOOST_STATIC_ASSERT() [1/3]
|
private |
§ BOOST_STATIC_ASSERT() [2/3]
|
private |
§ BOOST_STATIC_ASSERT() [3/3]
|
private |
§ compact()
|
protected |
compact item space, making all freed space available.
§ delete_item()
|
protected |
delete the given item, moving down items to take its place. E.g., deleting item 1 makes the old item 2, if any, now item 1 and so on. Compaction (compact()) may be required to make the freed space available.
§ delete_range()
|
protected |
delete the given range of items. This is used in a page split to delete the mived records from the overflowing page. "to" is an exclusive boundary, while "from" is inclusive, i.e., (from - to) items are deleted in total
§ eq()
| bool btree_page_data::eq | ( | const btree_page_data & | b | ) | const |
§ init_items()
|
protected |
Initialize item storage area, erasing any existing items. btree_level must be set before hand and not changed afterwards.
§ insert_item() [1/2]
|
protected |
Attempt to insert a new item at given item position, pushing existing items at and after that position upwards. E.g. inserting to item 1 makes the old item 1 (if any) now item 2, old item 2 (if any) now item 3, and so on. Item position may be one beyond the last existing item position (i.e., number_of_items()) in order to insert the new item at the end.
Returns false iff the insert fails due to inadequate available space (i.e., predict_item_space(data_length) > usable_space()).
The inserted item is a ghost iff ghost is set and has poor_man_key data poor, child child, and variable-length data of length data_length. child must be 0 if this is a leaf page.
The new item's variable-length data is allocated but not initialized.
§ insert_item() [2/2]
|
protected |
Attempt to insert a new item at given item position, pushing existing items at and after that position upwards. E.g. inserting to item 1 makes the old item 1 (if any) now item 2, old item 2 (if any) now item 3, and so on. Item position may be one beyond the last existing item position (i.e., number_of_items()) in order to insert the new item at the end.
Returns false iff the insert fails due to inadequate available space (i.e., predict_item_space(data_length) > usable_space()).
The inserted item is a ghost iff ghost is set and has poor_man_key data poor, child child, and variable-length data data. child must be 0 if this is a leaf page.
§ is_ghost()
|
inlineprotected |
is the given item a ghost?
§ is_leaf()
|
inlineprivate |
are we a leaf node?
§ item_child()
|
inlineprotected |
Return a reference to the child pointer data for the given item. The reference will be 4 byte aligned and thus a suitable target for atomic operations.
- Precondition
- this is an interior page
§ item_data()
|
inlineprotected |
return a pointer to the variable-length data of the given item
the variable length data occupies item_data(item) ... item_data(item)+item_length(item)-1
§ item_length()
|
inlineprotected |
return the amount of variable-length data belonging to the given item in bytes
§ item_poor() [1/2]
|
inlineprotected |
return the poor_man_key data for the given item
§ item_poor() [2/2]
|
inlineprotected |
return a reference to the poor_man_key data for the given item
§ item_space()
|
inlineprotected |
return total space currently occupied by given item, including any overhead such as padding for alignment.
§ number_of_ghosts()
|
inlineprotected |
return number of current items that are ghosts
§ number_of_items()
|
inlineprotected |
§ predict_item_space()
|
inlineprotected |
Calculate how much space would be occupied by a new item that was added to this page with data_length amount of variable-length data. (E.g., after insert, what will item_space return?)
§ remove_items()
|
protected |
§ replace_item_data()
|
protected |
Attempt to replace all the variable-length data of the given item after the first offset bytes with new_data, resizing the item's variable length data as needed. Returns false iff it fails due to inadequate available space.
- Precondition
- keep_old <= item_length(item)
§ resize_item()
|
protected |
Attempt to resize the variable-length data of the given item to new_length. Preserves only the first keep_old bytes of the old data; later bytes, if any, acquire undefined values. Returns false iff it fails due to inadequate available space. (Growing an item may require available space equivalent to inserting a new item of the larger size.)
- Precondition
- keep_old <= item_length(item)
§ set_ghost()
|
protected |
turn the given item into a ghost item
§ STATIC_LESS_THAN() [1/3]
|
private |
§ STATIC_LESS_THAN() [2/3]
|
private |
§ STATIC_LESS_THAN() [3/3]
|
private |
§ truncate_all()
|
protected |
remove 'amount' leading bytes from each item data, starting at offset 'pos"
Example: current data = AABBCC after truncate_all(2, 2) = AACC
§ unset_ghost()
|
protected |
turn the given item into a non-ghost item
§ unused_part()
|
protected |
returns the part of this page holding the available space; this region does not contain data and may be discarded when saving and filled with undefined values when restoring. Ideally, call compact() first when doing this to maximize the bytes that may be ignored. (See page_img_format_t for a use of this.)
§ usable_space()
|
inlineprotected |
Return amount of available space for inserting/resizing. Calling compact() may increase this number.
Friends And Related Function Documentation
§ operator<<
|
friend |
Member Data Documentation
§ @21
| union { ... } |
§ body
| item_body btree_page_data::body[max_bodies] |
§ btree_chain_fence_high_length
|
protected |
length of high-fence key of the foster chain. 0 if not in a foster chain or at the end of a foster chain. Corresponding data is stored in the first item after high fence key.
§ btree_consecutive_skewed_insertions
|
protected |
Count of consecutive insertions to right-most or left-most.
Positive values mean skews towards right-most. Negative values mean skews towards left-most. Whenever this page receives an insertion into the middle, this value is reset to zero. Changes of this value will NOT be logged. It doesn't matter in terms of correctness, so we don't care about undo/redo of this header item.
§ btree_fence_high_length
|
protected |
length of high-fence key. Corresponding data is stored in the first item after low fence key.
§ btree_fence_low_length
|
protected |
length of low-fence key. Corresponding data is stored in the first item.
§ btree_foster
|
protected |
Foster link page ID (0 if not linked).
§ btree_level
|
protected |
Level of this node in the B-tree, starting from the bottom with 1. In particular, 1 if we are a leaf and >1 if a non-leaf (interior) node.
§ btree_pid0
|
protected |
First child pointer in non-leaf nodes.
§ btree_prefix_length
|
protected |
Common prefix length for this page. All keys of this page except possibly the Foster key share (at least) this many prefix bytes.
btree_page_t compresses all keys except the low fence key and the Foster key by removing these prefix bytes.
§ btree_root
|
protected |
Page ID of the root page of the B-tree this node belongs to. The root page ID of a B-tree is never changed even while the tree grows or shrinks.
This field is redundant and could later be removed by replacing references to it with retrieving the root pid from pid via the stnode_cache_t associated with the volume pid.vol() by looking up store pid.store().
§ first_used_body
|
private |
offset to beginning of used item bodies (# of used item body that is located left-most).
§ head
§ max_item_overhead
|
staticprotected |
the maximum possible item overhead beyond a item's variable-length data. That is, item_space(X) <= max_item_overhead + X always.
§ nghosts
|
private |
number of current ghost items
§ nitems
|
private |
current number of items
§ padding
|
private |
padding to ensure header size is a multiple of 8
The documentation for this class was generated from the following files:
- src/sm/btree_page.h
- src/sm/btree_page.cpp
