caa a22 4500 465821596 CHVBK 20180323112137.0 cr unu---uuuuu 170327e19900601xx s 000 0 eng 10.1007/BF02017342 doi (NATIONALLICENCE)springer-10.1007/BF02017342 On the construction of weighted time-optimal B-trees [Elektronische Daten] [Shou-Hsuan Huang, Venkatraman Viswanathan] B-trees have been popular data structures since their definition. Their success is due to the fact that a B-tree containingn keys is "balanced” with a height ofO(logn). However, for a given set of elements and their access frequencies, one can construct many B-trees (possibly with different heights). The average access costs of these trees may vary significantly. An algorithm to construct a weighted time-optimal B-tree is presented. A weighted time-optimal B-tree is one in which the weighted access cost is minimized. A dynamic programming algorithm is used to construct a weighted time-optimal B-tree givenn elements and their weights. The algorithm runs in timeO(mn 3 logn) and has a storage requirement ofO(mn 2 logn) wherem is the order of the B-tree andn is the number of keys. BIT Foundations, 1990 I.2.8 nationallicence E.1 nationallicence H.3.3 nationallicence B-trees nationallicence optimality nationallicence node-visits nationallicence key-comparisons nationallicence Huang Shou-Hsuan Department of Computer Science, University of Houston, 77204-3475, Houston, Texas, USA aut Viswanathan Venkatraman Department of Computer Science, University of Houston, 77204-3475, Houston, Texas, USA aut BIT Kluwer Academic Publishers 30/2(1990-06-01), 207-215 0006-3835 30:2<207 1990 30 10543 https://doi.org/10.1007/BF02017342 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02017342 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Huang Shou-Hsuan Department of Computer Science, University of Houston, 77204-3475, Houston, Texas, USA aut NATIONALLICENCE 700 1- Viswanathan Venkatraman Department of Computer Science, University of Houston, 77204-3475, Houston, Texas, USA aut NATIONALLICENCE 773 0- BIT Kluwer Academic Publishers 30/2(1990-06-01), 207-215 0006-3835 30:2<207 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer