B-tree: Difference between revisions

Content deleted Content added

Revision as of 15:48, 8 December 2018 edit EEng (talk \| contribs) Edit filter helpers, Autopatrolled, Extended confirmed users, New page reviewers, Pending changes reviewers, Template editors 95,980 edits Undid revision 872683431 by 134.34.7.218 (talk) cited below Tag: Undo ← Previous edit		Revision as of 18:14, 8 December 2018 edit undo Glrx (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 29,697 edits →‎Best case and worst case heights: make h consistent Next edit →
Line 117: ==Best case and worst case heights== Let ''h'' be the height of the classic B-tree; let the root node be height 0. Let ''n'' > 0 be the number of entries in the tree.<ref>If ''n'' is zero, then no root node is needed, so the height of an empty tree is not well defined.</ref> Let ''m'' be the maximum number of children a node can have. Each node can have at most ''m''−1 keys. It can be shown (by induction for example) that a B-tree of height ''h'' with all its nodes completely filled has {{nowrap\|1=''n'' = ''m''<sup>''h''+1</sup>−1}} entries. Hence, the best case height of a B-tree is: : <math>h_{\mathrm{min}} = \lceil \log_{m} (n+1) \rceil -1</math> Let <math>d</math> be the minimum number of children an internal (non-root) node can have. For an ordinary B-tree, <math> d = \left\lceil m/2 \right\rceil. </math>