Pergunta

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: enter image description here

2-B+Tree without buckets at the end: enter image description here

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?

Foi útil?

Solução

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.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a dba.stackexchange
scroll top