{"entities":{"Q686641":{"pageid":688490,"ns":120,"title":"Item:Q686641","lastrevid":47193817,"modified":"2025-12-31T23:29:07Z","type":"item","id":"Q686641","labels":{"en":{"language":"en","value":"\\(B\\)-trees with inserts and deletes: Why free-at-empty is better than merge-at-half"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428584"}},"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":"Q686641$9B6DBBD7-363D-4423-A302-705DE469C106","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2a775cf759c36c3fded74c4a439ff3c623987b89","datavalue":{"value":{"text":"\\(B\\)-trees with inserts and deletes: Why free-at-empty is better than merge-at-half","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686641$3F985376-A05D-4E35-9DD3-84EE5F3DCD71","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"13126f5b49400b04667f055c1fbc54ecd3a6c5f5","datavalue":{"value":"0780.68016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686641$AE8A17D7-FAC5-4C73-A138-E17B60074606","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b0d1346216add4db54ad913d4ed652d9d611a86","datavalue":{"value":"10.1016/0022-0000(93)90020-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686641$337CD297-4516-4B83-BA77-3EF3841497A1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9af4dbca1d1149633ea983c50753e3279f9f3de3","datavalue":{"value":{"entity-type":"item","numeric-id":192209,"id":"Q192209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686641$B2D8CDA4-501B-4C17-875C-C2B0CE6EDA54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"376e8025bee4ddda1ce3474d3e3cdeeffcad5d3b","datavalue":{"value":{"entity-type":"item","numeric-id":686640,"id":"Q686640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686641$A86CD970-FBAC-4B0A-B219-32DEC52E2D24","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686641$90A3ACE7-3FFA-47E1-857E-9DBA730AFE0C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9ee486378a5fb0f84338329fe78e00d0957904b","datavalue":{"value":{"time":"+1993-10-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686641$85C22D91-0405-49A6-A7FB-530260B8B187","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d414aada008677b501b37f9b20cd3acc087e4efa","datavalue":{"value":"\\(B\\)-trees are a well-known and widely used data structure which allows efficient search in very large databases. A \\(B\\)-tree of parameter \\(p\\) is a balanced tree in which the distance between the root and any leaf is the same and any non-leaf mode has between 1 and \\(2p-1\\) children. The paper investigates the space utilization (i.e. the expected percentage of a node used to store data) under insertions and two policies of deletions: (1) free-at-empty, when a node is deleted when it becomes empty and the deletions are propagated upwards, and (2) merge-at-half, when a node becoming half empty after a deletion is merged with its neighbor. Analytical results are proved and simulation data is reported for these two strategies. The paper provides a simple rule of thumb, depending on the comparative rate of delete vs. insert operations, which indicates when one of the strategy is to be preferred.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686641$C210E7AF-9C5F-44D8-8727-07E9B660BA53","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fc8522c6547fe483c0d1ae4eec1b8d9306e5db1","datavalue":{"value":{"entity-type":"item","numeric-id":290243,"id":"Q290243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686641$4EDC6A1C-E1CD-477C-882C-6748B2899B8E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686641$166F7E22-A701-4400-8335-02A5BEBCEEF9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bd413fcfd173c603f91b8eabc178862c543263e2","datavalue":{"value":"428584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686641$0756AE64-7C1A-4076-B6B8-772428B8883E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"244fdf1b545d398536e29576058f09f76551e3cf","datavalue":{"value":"\\(B\\)-trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q686641$EF6B3237-D477-45D6-B707-AA6872E5A271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"164650a0152130384226de19a28e201d5e917d2c","datavalue":{"value":"space utilization","type":"string"},"datatype":"string"},"type":"statement","id":"Q686641$252EB2B4-2ED1-45EA-9A2D-979F89C60F0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d77162588362d38acc5567d3255fa45e1f8e7a25","datavalue":{"value":"insertions","type":"string"},"datatype":"string"},"type":"statement","id":"Q686641$FEFD1E1C-956B-4128-AE5C-93B18492945F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44d130647d012cc5557f5b67dcc52c6f8ab397b3","datavalue":{"value":"deletions","type":"string"},"datatype":"string"},"type":"statement","id":"Q686641$BB0B6F30-401B-4E5C-9392-24E37B7D73D7","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":"Q686641$C36A418A-4FA2-4955-AEB3-80B68BEAD8CF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"813b2660041f425224b3fd9c6a588267144808a7","datavalue":{"value":{"entity-type":"item","numeric-id":1105354,"id":"Q1105354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686641$1EBD8418-BC11-4366-813A-A1BB4E5A7753","rank":"normal"},{"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":"Q686641$BA8096C1-4736-4B3C-A665-64D40F4C701D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75ea186da56b084f21bdf3992f87ee7d4f3ff8d1","datavalue":{"value":{"entity-type":"item","numeric-id":1232296,"id":"Q1232296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686641$1F765F7B-0974-450C-8539-F6D9BC448506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2493450e87b44fdf55dd75491c860e2d04f0eb2","datavalue":{"value":{"entity-type":"item","numeric-id":1099971,"id":"Q1099971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686641$6D9350F0-521A-4E5C-A6A5-DD316E2CF320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4d998925a5c537818f135c90ae1fd4cac5f5d20","datavalue":{"value":{"entity-type":"item","numeric-id":5186749,"id":"Q5186749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686641$05363C85-17E5-43C4-AB33-14314B042A19","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":"Q686641$EBBB3BF8-3B85-4484-8576-5D04129D9464","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":"Q686641$0258C8EF-F58A-44EC-9A7F-B0F552F91836","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":"Q686641$182BCA0F-B31E-4DC8-AA88-063E75412EA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b09594c30b8ff839b25acc04b01e1e6a73469e47","datavalue":{"value":{"entity-type":"item","numeric-id":1123655,"id":"Q1123655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686641$C28FF455-4F91-499F-AA98-D49EA8154BB5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7e2fb455e9225c13ab94cf80779cf049f1591d92","datavalue":{"value":"https://doi.org/10.1016/0022-0000(93)90020-w","type":"string"},"datatype":"url"},"type":"statement","id":"Q686641$A5765DA9-EE74-4CBB-B498-7B4C68353517","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a2d265158007cb5cf2bbc9f5229e052998342ce1","datavalue":{"value":"W2069205797","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686641$3EE0A937-5170-4DB0-B71D-706232E60B94","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc7302ff9631f7e635585733dd536d44adf1c62b","datavalue":{"value":{"entity-type":"item","numeric-id":3652269,"id":"Q3652269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ca5167d1c468cd4ebf7705d2b3233080c9e6b08","datavalue":{"value":{"amount":"+0.7973090410232544","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":"Q686641$F42D01A8-5069-45F4-83EE-4D66FF1C5358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98760227b889c78eee1bd7d4d2a1eaacfa6b9f3a","datavalue":{"value":{"entity-type":"item","numeric-id":2943570,"id":"Q2943570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77e69f22baec7a4dd2e4f843450cb7e490b06362","datavalue":{"value":{"amount":"+0.7887507677078247","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":"Q686641$29A1438D-BFCF-4318-83C3-1CB05B7B96DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68718fa3a24d2e4f70b05d7a3ddeafb59db66dec","datavalue":{"value":{"entity-type":"item","numeric-id":1900545,"id":"Q1900545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f018a79c5c3a5cecb48c6f33c022a660dceb7e4","datavalue":{"value":{"amount":"+0.7866936326026917","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":"Q686641$823D63C6-B633-4BF0-8CAD-72CB9E3059AF","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":"2f018a79c5c3a5cecb48c6f33c022a660dceb7e4","datavalue":{"value":{"amount":"+0.7866936326026917","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":"Q686641$CBDDE6DC-AE23-4BB2-BCA1-5863AD3415BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bab02837421e23bf7978a154fc0613832992c763","datavalue":{"value":{"entity-type":"item","numeric-id":797287,"id":"Q797287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1a162eb470c26d9778cdba905de1ad373800bf7","datavalue":{"value":{"amount":"+0.7686931490898132","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":"Q686641$E0FC17A6-41E1-49E4-896E-2890DAC78244","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:686641","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:686641"}}}}}