{"schema_version":"4ort.packet/1","entity":{"entity_id":"b-tree","kg_uuid":"bc540e83-6142-4f12-91e2-7077c553387c","wikidata_id":"Q677051","name":"B-tree","description":"a self-balancing, tree-based data structure, that allows read/write access in logarithmic time","type":"CreativeWork","url":"https://4ort.xyz/entity/b-tree"},"status":"complete","as_of":{"copy_written_at":"2026-11-12T17:47:32Z","last_source_edit_seen":"2026-11-06T14:21:38Z","stale_possible":false,"claims_refreshed_at":"2026-11-06T14:21:55Z","source_revision":2565420370},"facts":[{"field":"P31","label":"instance of","value":"data structure","value_id":"Q175263","value_raw":"Q175263","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P31","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P279","label":"subclass of","value":"(a,b)-tree","value_id":"Q4544940","value_raw":"Q4544940","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P279","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"http://xlinux.nist.gov/dads//HTML/abtree.html","stated_in":"Dictionary of Algorithms and Data Structures","stated_in_id":"Q4423787","retrieved":"2015-04-11"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P279","label":"subclass of","value":"search tree","value_id":"Q621673","value_raw":"Q621673","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P279","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P279","label":"subclass of","value":"balanced tree","value_id":"Q29791656","value_raw":"Q29791656","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P279","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P279","label":"subclass of","value":"BV-tree","value_id":"Q29793859","value_raw":"Q29793859","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P279","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P279","label":"subclass of","value":"data structure","value_id":"Q175263","value_raw":"Q175263","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P279","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"French Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Rudolf Bayer","value_id":"Q66656","value_raw":"Q66656","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P61","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Edward M. McCreight","value_id":"Q10270906","value_raw":"Q10270906","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P61","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P575","label":"time of discovery or invention","value":"1972","value_id":null,"value_raw":"+1972-00-00T00:00:00Z","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P575","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"Organization and maintenance of large ordered indices","stated_in_id":"Q61783186"},{"imported_from":"English Wikipedia"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1245","label":"OmegaWiki Defined Meaning","value":"1704279","value_id":null,"value_raw":"1704279","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P1245","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1482","label":"Stack Exchange tag","value":"https://stackoverflow.com/tags/b-tree","value_id":null,"value_raw":"https://stackoverflow.com/tags/b-tree","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P1482","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1889","label":"different from","value":"binary tree","value_id":"Q380172","value_raw":"Q380172","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P1889","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2283","label":"uses","value":"tree","value_id":"Q223655","value_raw":"Q223655","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P2283","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2579","label":"studied by","value":"algorithmics","value_id":"Q13636890","value_raw":"Q13636890","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P2579","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2812","label":"MathWorld ID","value":"B-Tree","value_id":null,"value_raw":"B-Tree","rank":"normal","current":null,"qualifiers":[{"field":"P1810","label":"subject named as","value":"B-Tree"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P2812","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3752","label":"worst-case time complexity","value":"O(\\log n) (insertion)","value_id":null,"value_raw":"O(\\log n) (insertion)","rank":"normal","current":null,"qualifiers":[{"field":"P13044","label":"characteristic of","value":"insert"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P3752","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3752","label":"worst-case time complexity","value":"O(\\log n) (suppression)","value_id":null,"value_raw":"O(\\log n) (suppression)","rank":"normal","current":null,"qualifiers":[{"field":"P13044","label":"characteristic of","value":"delete"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P3752","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3752","label":"worst-case time complexity","value":"O(\\log n) (recherche)","value_id":null,"value_raw":"O(\\log n) (recherche)","rank":"normal","current":null,"qualifiers":[{"field":"P13044","label":"characteristic of","value":"search"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P3752","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3754","label":"average time complexity","value":"O(\\log n)","value_id":null,"value_raw":"O(\\log n)","rank":"normal","current":null,"qualifiers":[{"field":"P13044","label":"characteristic of","value":"insert"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P3754","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3754","label":"average time complexity","value":"O(\\log n)","value_id":null,"value_raw":"O(\\log n)","rank":"normal","current":null,"qualifiers":[{"field":"P13044","label":"characteristic of","value":"delete"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P3754","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3754","label":"average time complexity","value":"O(\\log n)","value_id":null,"value_raw":"O(\\log n)","rank":"normal","current":null,"qualifiers":[{"field":"P13044","label":"characteristic of","value":"search"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P3754","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3755","label":"worst-case space complexity","value":"O(n)","value_id":null,"value_raw":"O(n)","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P3755","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3757","label":"average space complexity","value":"O(n)","value_id":null,"value_raw":"O(n)","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P3757","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5106","label":"Dictionary of Algorithms and Data Structures ID","value":"btree","value_id":null,"value_raw":"btree","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P5106","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5106","label":"Dictionary of Algorithms and Data Structures ID","value":"balancedMultiwayTree","value_id":null,"value_raw":"balancedMultiwayTree","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P5106","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6104","label":"maintained by WikiProject","value":"WikiProject Mathematics","value_id":"Q8487137","value_raw":"Q8487137","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P6104","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6366","label":"Microsoft Academic ID (discontinued)","value":"78669399","value_id":null,"value_raw":"78669399","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P6366","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P7726","label":"PlanetMath ID","value":"Btree","value_id":null,"value_raw":"Btree","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q677051#P7726","source_edition":"2026-11-06T14:21:55Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}}],"unknowns":[],"omitted":{"facts":0,"reason":null},"licences":[{"source":"wikidata","source_name":"Wikidata","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"fields":["P31","P279","P61","P575","P1245","P1482","P1889","P2283","P2579","P2812","P3752","P3754","P3755","P3757","P5106","P6104","P6366","P7726"]}],"routes":{"entity_page":"https://4ort.xyz/entity/b-tree","packet_api":"https://4ort.xyz/api/v1/entities/b-tree/packet","facts_jsonld":"https://4ort.xyz/entity/b-tree/facts.json","changes_api":"https://4ort.xyz/api/v1/knowledge/get_entity_changes?entity=b-tree","attention_api":"https://4ort.xyz/api/v1/knowledge/get_attention?entity=b-tree","wikidata":"https://www.wikidata.org/wiki/Q677051","official_website":null},"trust_rules":{"wikidata-reference-support/2":"From the references in our copy of the statement: high = it cites a source (stated in P248, or a reference URL that is not Wikipedia); medium = only 'imported from Wikimedia project' or a Wikipedia URL; unscored = our copy holds no reference (older copies dropped references, so this is not evidence that Wikidata has none). Wikidata may hold more references than our copy shows. Reference support, not a probability."},"notes":[]}