Hot answers tagged

3

One thing that distinguishes real-world B-trees from "lecture B-trees" is that real B-trees tend to have nodes and leaves where the size in bytes is fixed. So the "degree" of a B-tree is determined by the number of keys that will fit on a page. So if the keys vary in size (e.g. strings), the "degree" of different nodes may be different. Roughly 50% of them ...


2

I don't think there's a right answer to this but you could argue for a preference either way. Let's define B-tree order m like this max children/values m min children/values m/2 max keys m-1 min keys Math.ceil(m/2)-1 Math.ceil is only needed if m is odd If m is even, the you have an odd number of keys. For example [a b c], we could split this either [a b]...


2

Every node contains between $\lceil(m/2)\rceil-1$ and $m-1$ keys (where m is the degree), so we can say that every node has between $\lceil(m/2)\rceil$ and $m$ children. If we imagine to construct a minimun nodes b-tree, we'll have: $n = 1 + 2 + 2\lceil m/2\rceil + 2\lceil m/2\rceil^2 + ... + 2\lceil m/2\rceil^{h-2}$where every addend is the number of nodes ...


1

There's an indeed a relation that maps the database keys to the B-trees keys $K_d \mapsto K_b, K_b \in \mathbb{Z}$ The B-Tree keys are not random though, they represent the physical location of data stored for that key. At the leaf level there are multiple ( up to the order of the tree) database $K_d$s associated with a single $K_b$ key. The relation is ...


1

There is no advantage to choosing one over the other. "Real" B+-tree implementations will often rebalance if they can, rather than splitting. When a node becomes overfull, if there is a sibling (whether to the left or the right) which isn't yet full, it's often better to balance the entries evenly between this node and its sibling. This saves an allocation.


1

Augment each node to contain the key of the node with maximum value, among all nodes that are underneath it (among all of its descendants). You can easily maintain/update this augmented information each time you modify the tree, by using the fact that the maximum for any node can be recomputed using just the information in its direct children (you don't ...


1

Because it keeps the B-tree balanced? In essence, what you are asking is why the algorithm is the way it is. The algorithm we use has been around long enough that if there was a better way to do it, people would have suggested that by now. I believe that the reason why this is the case is that the current algorithm is the simplest way possible to solve the ...


1

Yes and yes. Any key that doesn't mess up the sort order can be used. Typically (in my experience), this is the minimum value from the right subtree. However, I'm not aware of any specific scenario where this would cause a problem either way. When you delete a key (one practice I have seen is that) you delete the key along with the value. So, if you delete ...


Only top voted, non community-wiki answers of a minimum length are eligible