B+ Tree structure with buckets (Begginer question)
-
04-10-2020 - |
문제
I am enrolled in a course and I am confused about few concepts in the structure of the B+Tree. I know what it does and what's the difference between it and BTree, but I got a bit conflicted when I saw 2 different examples:
1-B+Tree with buckets at the end:
2-B+Tree without buckets at the end:
Example 2 is the most popular example I noticed on the web. My instructor told me that in example 2 the pointers of the leaves can point to buckets too, but wait a second it would be the same as the first example but with the last pointer to the left going to the next leaf.
Question: Is it mandatory for a b+tree leaf to have a pointer towards the next leaf?
My instructor told me to make it easier on myself to assume the bucket as a leaf that has a pointer towards the next bucket. It's better not to understand something on understanding something using a wrong way.
There's this clash inside me about the B+tree structure. Is there more than one structure for a b+tree?
해결책
It is not mandatory for a b+tree leaf to have a pointer towards the next leaf, but it is a widely used optimization to allow efficient scanning of value ranges, such as, in the context of relational databases, supporting WHERE field BETWEEN x AND y
or WHERE field > x
predicates. Frequently you see a leaf pointing to both next and previous leaves, supporting bidirectional scanning as well (for WHERE field < x
). Apart from the search predicate support, it may also be useful for record ordering and aggregation.