{"entities":{"Q797287":{"pageid":799135,"ns":120,"title":"Item:Q797287","lastrevid":64448364,"modified":"2026-04-11T19:56:45Z","type":"item","id":"Q797287","labels":{"en":{"language":"en","value":"Some average performance measures for the B-tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3868631"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$BCCDE0AC-06EE-441B-8A2E-D7720F094F3C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f5a5b1bce40497881b85f285a79dcc39feeef68e","datavalue":{"value":{"text":"Some average performance measures for the B-tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q797287$0C5EEB31-993C-46F6-995B-79A3C4AED9A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8611e0efbde13683fd36c1d59a916dfd2bfa8236","datavalue":{"value":"0545.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797287$2E658CB2-EDF3-4B7D-B5F5-9EDD97C7EB70","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"91ab089bb488e64078305ee634cb67420fc673e0","datavalue":{"value":"10.1007/BF00289710","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797287$E8B9A0D5-E210-4E55-8955-45789973574A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9f3bf23eea3ab29e241c112c61a307dcbe6724ae","datavalue":{"value":{"entity-type":"item","numeric-id":294673,"id":"Q294673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$9A70882D-6AEC-4BCD-BB96-E9151F47C4DE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$65B4A79F-8538-426D-B869-7FB94FF47EC6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q797287$A2B06504-78D3-4B05-AD3D-69769E11C209","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d6ed951c22974a7597b67c432722ce8da4b08a44","datavalue":{"value":"Several average performance measures are presented for large B-trees formed from insertions, where large refers to the number of keys. Formulas are first derived for the expected number of nodes of each size on the bottom level of the tree, where the size of a node is the number of keys currently contained in the node. This is followed by formulas for the probability of making an insertion into a node of a given size, the probability of a split during an insertion into a node, and the expected number of splits during an insertion into the tree. Is is shown that for large trees of high order m, the expected number of splits per insertion is approximately \\(1/(\\ln 2)m).\\) A formula is presented for the average storage utilization, and it is shown that this average approaches ln 2 as m approaches infinity. A simpler formula is derived for the average storage utilization at the bottom level of the tree, and it is shown that this formula is an increasing function of m ranging from 2/3 to ln 2. It is shown that the expected tree height and the expected search path length are approximately logarithmic to the base (ln 2)m. Simulation results are presented to corroborate the theoretical analysis.","type":"string"},"datatype":"string"},"type":"statement","id":"Q797287$E07678B2-445B-46E3-908C-71C825C71636","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797287$C25B3F7C-1BA0-4207-8722-EB6AC504AC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797287$D5C5DE6F-8503-419A-8FB3-7D795DB6119F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797287$98D98516-F790-46BB-8CF0-3C6D455CB2E4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b9a8ac9388a53ccb21aa579cf12dceac197a008","datavalue":{"value":"3868631","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797287$25732AF1-7E19-4C52-A6AB-D88E5FB42A27","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2808a02e1d54b658348f02a9e3cf4ee2f0b6d79","datavalue":{"value":"multiway trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q797287$B7BABFA7-3A19-4CDD-955E-48D9D6515EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d6d7de2e591a8b33485f03db6bb19cb001f8768","datavalue":{"value":"indexes","type":"string"},"datatype":"string"},"type":"statement","id":"Q797287$B1AE1530-7656-4361-B29E-B15058CF61CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eebd9e840bd8d577f9e8c8c6082917fafb529146","datavalue":{"value":"file organization","type":"string"},"datatype":"string"},"type":"statement","id":"Q797287$2ED66650-D369-42E3-B464-9A872E6DCC18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a30f451ce735cfc24e918247495c3c18f5a4d960","datavalue":{"value":"average performance measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q797287$60F72856-36B6-4B2B-90CD-750F8BCAC03E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab5d352ea7839f8594a5c9725b8a641858d27282","datavalue":{"value":"large B-trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q797287$CD081659-8B5C-4208-9556-FB01116A44C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f465ed1d9a1ecaaf5ab28c7b8822d030b27f6f65","datavalue":{"value":"average storage utilization","type":"string"},"datatype":"string"},"type":"statement","id":"Q797287$5D71286B-421D-4BA1-BA71-716B82D4AFAF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$E2CDCA82-0BA9-4292-9DBB-C2EC47968BAF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef146def2d585ff66e37bf85e5bd822184c47a27","datavalue":{"value":{"entity-type":"item","numeric-id":2549238,"id":"Q2549238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$64E2FE46-79EF-4B6A-86B8-E2CB7C2EA64F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06c497d8d4d5276796a1d082d212aae5a8376e1a","datavalue":{"value":{"entity-type":"item","numeric-id":4144191,"id":"Q4144191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$2FD5E92E-E023-4283-9A57-CE630B7C3AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa0540fd78fb7a7ac36ecb95287d9deaac0fb1e2","datavalue":{"value":{"entity-type":"item","numeric-id":5585021,"id":"Q5585021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$A776E5D0-ED20-49B9-AFF6-192C33B96B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$0316CA81-6A36-48CB-8F5E-55531D88214C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c056001981861f2a7c86d0a9b87bd155bc3046b3","datavalue":{"value":{"entity-type":"item","numeric-id":1172382,"id":"Q1172382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$B8F80F06-113C-4523-9462-44EE6559B7FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bc08fc0da5041a8c9a29fd1cb79673911483b8b","datavalue":{"value":{"entity-type":"item","numeric-id":1138915,"id":"Q1138915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$431DA6EF-28F3-4C7D-AE9D-0E2B63158AEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44bc767850337e21a183ed9e8b9103abf049f928","datavalue":{"value":{"entity-type":"item","numeric-id":3206351,"id":"Q3206351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$5B70EAE3-6607-4050-9997-B15D702F4FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf09bd96511964db0c61b9a482c9900ab63e5c4d","datavalue":{"value":{"entity-type":"item","numeric-id":1243733,"id":"Q1243733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797287$1EC732B8-19CC-4394-9785-A27B4A6E39E8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6c033f02e37f0f694e4237ce0346a5e11ef00744","datavalue":{"value":"https://doi.org/10.1007/bf00289710","type":"string"},"datatype":"url"},"type":"statement","id":"Q797287$F8B0C971-EB16-4F93-8239-5DE8EC1FE19F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2c1b1da5c2f0904d283b5d259a5fd4821056b263","datavalue":{"value":"W1978071187","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797287$6CFF75AF-9205-4C1B-BA58-657488E7CBD2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52308edddc5ad90a3dc55178f9f20e710648b16c","datavalue":{"value":{"entity-type":"item","numeric-id":1117687,"id":"Q1117687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e753d6e8f720a19bf224d9dc9719e9dce5845d3","datavalue":{"value":{"amount":"+0.883054792881012","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797287$514CD78C-B258-4F19-8FE5-C732D88DB76E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40186040c8ed686df3d69941f7ad11a77d155c1e","datavalue":{"value":{"entity-type":"item","numeric-id":1105354,"id":"Q1105354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7866823b8450b5e939584566a43c4ad61c274a0","datavalue":{"value":{"amount":"+0.8572925925254822","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797287$D84B78A3-8A47-4B48-98E8-68FB1D761E0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"628b742f1df059bd52921f94fa4729be75ff644f","datavalue":{"value":{"entity-type":"item","numeric-id":3685211,"id":"Q3685211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aaed2038227a74b3949e91b1c53c3c7c8e3ec0f","datavalue":{"value":{"amount":"+0.8151781558990479","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797287$99372473-9953-4EB9-940F-DA23863AEB44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3881cdb0ba4b65174b02a06fe43d28222a2af947","datavalue":{"value":{"entity-type":"item","numeric-id":1099971,"id":"Q1099971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eec7a2cabc2103029d49bad235da24a4ff8c928c","datavalue":{"value":{"amount":"+0.8149567246437073","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797287$FEE8FFBD-E6F7-4284-B6D8-824E6506273F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6abb709b788efdb173f36c2908e99fab55422964","datavalue":{"value":{"entity-type":"item","numeric-id":2805318,"id":"Q2805318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"330612343e9b21282e91e26c62a8b9f8cb201316","datavalue":{"value":{"amount":"+0.8056322336196899","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797287$7BCF695A-2AD4-4238-A40A-8185AC10C538","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some average performance measures for the B-tree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_average_performance_measures_for_the_B-tree"}}}}}