12 B-TREES Flashcards by Kaman Hung

What is the primary purpose of B-trees?

To manage the cost of retrieving new blocks of data.

How well did you know this?

Not at all

Perfectly

What is a page in the context of data retrieval?

An entire block of information read from the hard drive and stored in memory.

How well did you know this?

Not at all

Perfectly

Who designed the B-tree data structure?

Rudolf Bayer and Edward McCreight.

How well did you know this?

Not at all

Perfectly

What is the tradeoff of using B-trees?

Additional complexity when dealing with the nodes.

How well did you know this?

Not at all

Perfectly

What is the size parameter ‘k’ in a B-tree?

It defines the bounds on how many elements a non-root node can store.

How well did you know this?

Not at all

Perfectly

What is the minimum and maximum number of keys a non-root B-tree node can store?

Between k and 2k keys.

How well did you know this?

Not at all

Perfectly

What is the maximum number of keys a root node in a B-tree can store?

Between 0 and 2k keys.

How well did you know this?

Not at all

Perfectly

How do internal nodes in a B-tree determine the ranges for branches?

Using the values of the keys to define the ranges.

How well did you know this?

Not at all

Perfectly

What is the balancing property of B-trees?

Every leaf node is at the same depth from the root.

How well did you know this?

Not at all

Perfectly

How are B-tree nodes structured?

They contain keys, pointers to children, and flags for leaf status.

How well did you know this?

Not at all

Perfectly

What analogy is used to explain the benefit of packing multiple items into a B-tree node?

Shipping costs for multiple small boxes versus packing several items into one box.

How well did you know this?

Not at all

Perfectly

What is the role of pointers in B-trees?

To link keys to corresponding child nodes and to manage the structure.

How well did you know this?

Not at all

Perfectly

What is the process for searching a B-tree?

Start at the root and work down, checking keys and descending to child nodes as needed.

How well did you know this?

Not at all

Perfectly

True or False: B-trees allow only two branches per node.

False.

How well did you know this?

Not at all

Perfectly

What is the expected runtime benefit of searching within a B-tree node?

Data accesses within a node are relatively cheap because they occur in local memory.

How well did you know this?

Not at all

Perfectly

What happens when a B-tree node becomes overfull during insertion?

The node is split to maintain balance.

How well did you know this?

Not at all

Perfectly

Fill in the blank: In a B-tree, internal nodes can have between _____ and _____ children.

k + 1 and 2k + 1.

How well did you know this?

Not at all

Perfectly

What is a potential downside of storing index cards in sorted order compared to using a B-tree?

Requires cascading updates to many binders as cards must be shifted over.

How well did you know this?

Not at all

Perfectly

What two approaches can be taken when a B-tree node is full during insertion?

Split as we proceed down the tree
Insert temporarily into a full node and split on the way back up.

How well did you know this?

Not at all

Perfectly

What type of data structure is used to define B-trees?

A composite data structure with nodes and size parameters.

How well did you know this?

Not at all

Perfectly

What is the significance of the B-tree’s multi-way branching structure?

It allows for more than two branches and maximizes data retrieval efficiency.

How well did you know this?

Not at all

Perfectly

What occurs when searching for a key that does not exist in a B-tree?

The search returns null if the current node is a leaf.

How well did you know this?

Not at all

Perfectly

What is the first step in the B-tree insertion algorithm?

Proceed down the tree, searching for the position to insert the new key.

How well did you know this?

Not at all

Perfectly

What happens if a node becomes overfull during a B-tree insertion?

The node is split on the way back up the tree.

How well did you know this?

Not at all

Perfectly

When does the height of a B-tree increase?

Only when the root node is split.

What is the purpose of the BTreeNodeAddKey function?

To insert a key into a non-full node.

What does the BTreeNodeIsOverFull function check?

Whether a node contains more than 2k items.

Fill in the blank: The maximum number of elements per node in a B-tree is _______.

What is the role of the BTreeNodeSplit function?

To split an overfull child node into two nodes.

How does the insertion function BTreeNodeInsert operate?

It recursively searches for the correct location to insert a new key and checks for overfull nodes.

True or False: The B-tree property can be broken by inserting too many elements into a node.

True

What does the wrapper function BTreeInsert do?

Handles the special case of splitting the root node and increasing the height of the tree.

What does the total work for a B-tree insertion scale with?

Proportional to k × log k (N).

What happens when a key is added to a leaf node that is not overfull?

The key is added directly to the leaf node without splitting.

In the case of adding a key to an overfull leaf node, what is the first step taken?

Identify the split point and promote it to the parent node.

What is the result of splitting the root node in a B-tree?

A new root node is created that contains exactly one key.

What is the significance of the variable 'k' in a B-tree?

It determines the minimum and maximum number of children per node.

True or False: A B-tree always remains balanced.

True

What is the result of promoting the middle element of an overfull node?

It may cause the parent node to become overfull, necessitating a split.

How does the B-tree ensure that all leaf nodes remain at the same depth?

By performing splits as needed and only increasing height when splitting the root.

What does the term 'branching factor' refer to in a B-tree?

The number of children a node can have, which is at least k + 1 for non-root nodes.

Fill in the blank: The B-tree insertion process can be visualized as adding a new _______ to a collection.

coffee mug

What is the key feature of the B-tree that allows it to efficiently handle insertions?

It allows temporary overfilling of nodes.

What is the function of the 'next_child' pointer in the BTreeNodeAddKey function?

To represent the child after the new key for reuse during node splitting.

What is the impact of a B-tree's balance on its performance?

It ensures logarithmic scaling in node retrievals.

What happens when the root node of a B-tree becomes overfull?

It is split into two siblings and the middle element is promoted to the new root node.

What is the range of keys that can be stored in each node of a B-tree?

Between k and 2k.

What is the first step in the multi-stage algorithm for deleting keys in a B-tree?

Proceed down the tree as though searching for the key.

What is used to check if a B-tree node is under-full?

BTreeNodeIsUnderFull(BTreeNode: node) returns node.size < node.k.

What are the two approaches to fixing an under-full node in a B-tree?

* Merge two small sibling nodes into a single node * Transfer a key from a larger sibling to the under-full node

What condition must be met to merge two adjacent sibling nodes in a B-tree?

The combined number of keys in the two siblings must be less than 2k.

What does the merge operation do in a B-tree?

It concatenates two adjacent sibling nodes into a single large child node.

What happens when merging two nodes in a B-tree?

A key from their parent is taken, which could leave the parent node with less than k keys.

What is the purpose of the BTreeNodeTransferLeft function?

To transfer a key from the right child to the left child in a B-tree.

What does the BTreeNodeTransferRight function accomplish?

It transfers a key from the left child to the right child in a B-tree.

What does the BTreeNodeRepairUnderFull function do?

It determines which repair strategy to employ for an under-full node.

What does the BTreeNodeFindMin function do?

It finds and returns the minimum key at or below a given node.

What happens when the root node of a B-tree becomes empty?

It is replaced by its only child.

What is the core of the deletion algorithm in a B-tree?

It recursively descends the tree searching for the key to delete.

Fill in the blank: The total number of modified nodes during an insertion in a B-tree scales proportional to _______.

log k (N)

True or False: We can remove a node from a B-tree except for an empty root node.

False.

What does the deletion process in a B-tree ensure?

The tree remains balanced.

What must be checked after deleting a key in a B-tree?

Whether the modified child is now under-full.

What is the initial action taken in the BTreeDelete function?

It calls the recursive deletion function using the tree's root node.

What happens to the root node when it becomes empty in a B-tree?

The empty root node will still have a single valid child in array position 0, which replaces the former root node.

What is the purpose of the core deletion algorithm in a B-tree?

To recursively descend the tree searching for the key to delete and check if the modified child is under-full, repairing it if necessary.

What is the process for deleting a key from a leaf node in a B-tree?

Shift over the keys to remove the target key, set the last element to null, and update the size.

What happens if the key to be deleted is found in an internal node of a B-tree?

Replace the key with the key that immediately follows it in sorted order and delete the following key from the child’s subtree.

What is the result of deleting a key from a B-tree leaf node that has more than k + 1 keys?

The leaf node remains valid and does not require repairs.

What occurs when deleting a key from an internal node without needing repairs?

The key is replaced with the next key in order, and no repairs are needed as all nodes remain valid.

What is the outcome when deleting a key causes an under-full node?

The node may need to merge with an adjacent sibling or transfer a key from a sibling to restore balance.

What is the significance of maintaining at least k keys in each non-root node of a B-tree?

It ensures a branching factor of at least k + 1, limiting the overall depth of the tree.

How does a B-tree adapt to the distribution of data it stores?

It constantly rearranges its structure to remain balanced by rebalancing nodes with too many or too few items.

What happens when the only two children under the root node are merged in a B-tree?

The root node becomes empty, and the single child of the merged node is promoted to be the new root.

True or False: Deletion in a B-tree can modify nodes in branches other than the one where the key was found.

True.

Fill in the blank: B-trees minimize the number of _______ needed for operations.

[memory accesses]

What is a potential tradeoff when optimizing a data structure for a specific task?

Loss of generalizability to apply it to other problems.

What do B-trees illustrate about balancing strategies for trees?

They provide a simple example of using multiple keys per node to avoid worst-case scenarios.

What is the maximum number of nodes modified during a deletion operation in a B-tree?

At most, one sibling node per level, scaling logarithmically with N.

What is the result of deleting a key from an almost empty node in a B-tree?

The node may need to merge with an adjacent sibling to restore the B-tree conditions.