oracleindexingb-tree

Oracle index use b-tree or b+tree by default?


I am studying about Oracle internals and I am wondering if the "B-tree index" stated on the documentation is actually classic B-tree or a B+tree?

I think is a B+tree because all data nodes are stored on the leaf nodes. Moreover the documentation day "B-tree" so I am not sure.


Solution

  • The documentation doesn't use the term "B+ tree" but it does describe its tree structure in some detail, and indeed what they describe is generally called B+ tree.

    For example, from the documentation for an old version (11.2):

    Branch Blocks and Leaf Blocks

    A B-tree index has two types of blocks: branch blocks for searching and leaf blocks that store values. The upper-level branch blocks of a B-tree index contain index data that points to lower-level index blocks. In Figure 3-1, the root branch block has an entry 0-40, which points to the leftmost block in the next branch level. This branch block contains entries such as 0-10 and 11-19. Each of these entries points to a leaf block that contains key values that fall in the range.

    https://docs.oracle.com/cd/E11882_01/server.112/e40540/indexiot.htm#CNCPT721

    The better question is, "why doesn't Oracle use the term B+ tree". It's possible that Oracle's implementation of the data structure is not exactly the one prescribed in textbooks. They may have proprietary optimizations that they don't want to discuss, and they may not have implemented some features of B+ trees (or implemented them differently from the standard specification). Who knows. In any case, even if the structure they use is not the textbook B+ tree, it is a form of B+ tree as you suspected.