Developed by Ed McCreight and Rudolf Bayer, it is a more generalized form of a 2-3 tree.
The Tetris Algorithm can be used to perform a range query on the universal type of these data structures, which make use of a Z Order Curve. A function which compares only the first k bits of data can be used to implement the space-saving prefix type of these data structures, while the regular type places elements to the left and right of a median node during the split portion of data insertion. A. A. Toptsis developed a variant of this data structure which increased the density of certain components within it to two thirds from another variant's one half, the so called star variety. In that latter variant, records are only stored at the leaf level, that is, the plus variety of this data structure, which is used to implement the NTFS file system. Developed by Ed McCreight and Rudolf Bayer, it is a more generalized form of a 2-3 tree. For 10 points, name this data structure, a type of self-balancing tree often used to implement databases.
The Tetris Algorithm can be used to perform a range query on the universal type of these data structures, which make use of a Z Order Curve.
B-Tree [or B Minus Tree]