B-Tree
المؤلف:
Aho, A. V.; Hopcroft, J. E.; and Ullmann, J. D
المصدر:
Data Structures and Algorithms. Reading, MA: Addison-Wesley
الجزء والصفحة:
...
19-5-2022
2379
B-Tree
-trees were introduced by Bayer (1972) and McCreight. They are a special 
-ary balanced tree used in databases because their structure allows records to be inserted, deleted, and retrieved with guaranteed worst-case performance. An 
-node 
-tree has height 
, where lg is the logarithm to base 2. The Apple® Macintosh® (Apple, Inc., Cupertino, CA) HFS filing system uses 
-trees to store disk directories (Benedict 1995). A 
-tree satisfies the following properties:
1. The root is either a tree leaf or has at least two children.
2. Each node (except the root and tree leaves) has between ![[m/2]](https://mathworld.wolfram.com/images/equations/B-Tree/Inline8.svg)
and 
children, where ![[x]](https://mathworld.wolfram.com/images/equations/B-Tree/Inline10.svg)
is the ceiling function.
3. Each path from the root to a tree leaf has the same length.
Every 2-3 tree is a 
-tree of order 3. The number of 
-trees of order 3 with 
, 2, ... leaves are 1, 1, 1, 1, 2, 2, 3, 4, 5, 8, 14, 23, 32, 43, 63, ... (Ruskey, OEIS A014535). The number of order-4 
-trees with 
, 2, ... leaves are 1, 1, 1, 2, 2, 4, 5, 9, 15, 28, 45, ... (OEIS A037026).
REFERENCES
Aho, A. V.; Hopcroft, J. E.; and Ullmann, J. D. Data Structures and Algorithms. Reading, MA: Addison-Wesley, pp. 369-374, 1987.
Bayer, R. and McCreight, E. "Organization and Maintenance of Large Ordered Indexes." Acta Informatica 1, 173-189, 1972.
Benedict, B. Using Norton Utilities for the Macintosh. Indianapolis, IN: Que, pp. B-17-B-33, 1995.
Beyer, R. "Symmetric Binary 
-Trees: Data Structures and Maintenance Algorithms." Acta Informat. 1, 290-306, 1972.
Knuth, D. E. "B-Trees." The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, pp. 482-485 and 490-491, 1998.
Ruskey, F. "Information on B-Trees." http://www.theory.csc.uvic.ca/~cos/inf/tree/BTrees.html.Skiena, S. S. The Algorithm Design Manual. New York: Springer-Verlag, p. 178, 1997.
Sloane, N. J. A. Sequences A014535 and A037026 in "The On-Line Encyclopedia of Integer Sequences."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
