CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>B-tree - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"9273cb8f-f604-4a21-ba2e-9fb0a6616ca1","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"B-tree","wgTitle":"B-tree","wgCurRevisionId":1259002079,"wgRevisionId":1259002079,"wgArticleId":4674,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 maint: multiple names: authors list","Articles with short description","Short description matches Wikidata","Wikipedia articles with style issues from May 2022","All articles with style issues","Wikipedia articles needing clarification from February 2012","All Wikipedia articles needing clarification","All articles with specifically marked weasel-worded phrases","Articles with specifically marked weasel-worded phrases from September 2019","Articles needing additional references from April 2018", "All articles needing additional references","All articles with unsourced statements","Articles with unsourced statements from October 2009","Articles needing additional references from May 2020","CS1: long volume value","Commons category link is on Wikidata","Webarchive template wayback links","B-tree","Computer-related introductions in 1971","Database index techniques"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"B-tree","wgRelevantArticleId":4674,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true, "tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":50000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q677051","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready", "jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="B-tree - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/B-tree"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=B-tree&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/B-tree"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-B-tree rootpage-B-tree skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=B-tree" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=B-tree" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=B-tree" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=B-tree" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-History" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#History"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>History</span> </div> </a> <ul id="toc-History-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Definition" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Definition</span> </div> </a> <button aria-controls="toc-Definition-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Definition subsection</span> </button> <ul id="toc-Definition-sublist" class="vector-toc-list"> <li id="toc-Differences_in_terminology" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Differences_in_terminology"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Differences in terminology</span> </div> </a> <ul id="toc-Differences_in_terminology-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Informal_description" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Informal_description"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Informal description</span> </div> </a> <button aria-controls="toc-Informal_description-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Informal description subsection</span> </button> <ul id="toc-Informal_description-sublist" class="vector-toc-list"> <li id="toc-Node_structure" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Node_structure"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Node structure</span> </div> </a> <ul id="toc-Node_structure-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Insertion_and_deletion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Insertion_and_deletion"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Insertion and deletion</span> </div> </a> <ul id="toc-Insertion_and_deletion-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Comparison_to_other_trees" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Comparison_to_other_trees"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Comparison to other trees</span> </div> </a> <ul id="toc-Comparison_to_other_trees-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Variants" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Variants"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.4</span> <span>Variants</span> </div> </a> <ul id="toc-Variants-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-B-tree_usage_in_databases" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#B-tree_usage_in_databases"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>B-tree usage in databases</span> </div> </a> <button aria-controls="toc-B-tree_usage_in_databases-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle B-tree usage in databases subsection</span> </button> <ul id="toc-B-tree_usage_in_databases-sublist" class="vector-toc-list"> <li id="toc-Time_to_search_a_sorted_file" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Time_to_search_a_sorted_file"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Time to search a sorted file</span> </div> </a> <ul id="toc-Time_to_search_a_sorted_file-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-An_index_speeds_the_search" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#An_index_speeds_the_search"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>An index speeds the search</span> </div> </a> <ul id="toc-An_index_speeds_the_search-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Insertions_and_deletions" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Insertions_and_deletions"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.3</span> <span>Insertions and deletions</span> </div> </a> <ul id="toc-Insertions_and_deletions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Advantages_of_B-tree_usage_for_databases" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Advantages_of_B-tree_usage_for_databases"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.4</span> <span>Advantages of B-tree usage for databases</span> </div> </a> <ul id="toc-Advantages_of_B-tree_usage_for_databases-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Best_case_and_worst_case_heights" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Best_case_and_worst_case_heights"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Best case and worst case heights</span> </div> </a> <ul id="toc-Best_case_and_worst_case_heights-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Algorithms" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Algorithms"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Algorithms</span> </div> </a> <button aria-controls="toc-Algorithms-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Algorithms subsection</span> </button> <ul id="toc-Algorithms-sublist" class="vector-toc-list"> <li id="toc-Search" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Search"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.1</span> <span>Search</span> </div> </a> <ul id="toc-Search-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Insertion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Insertion"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2</span> <span>Insertion</span> </div> </a> <ul id="toc-Insertion-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Deletion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Deletion"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.3</span> <span>Deletion</span> </div> </a> <ul id="toc-Deletion-sublist" class="vector-toc-list"> <li id="toc-Deletion_from_a_leaf_node" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Deletion_from_a_leaf_node"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.3.1</span> <span>Deletion from a leaf node</span> </div> </a> <ul id="toc-Deletion_from_a_leaf_node-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Deletion_from_an_internal_node" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Deletion_from_an_internal_node"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.3.2</span> <span>Deletion from an internal node</span> </div> </a> <ul id="toc-Deletion_from_an_internal_node-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Rebalancing_after_deletion" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Rebalancing_after_deletion"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.3.3</span> <span>Rebalancing after deletion</span> </div> </a> <ul id="toc-Rebalancing_after_deletion-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Sequential_access" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Sequential_access"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.4</span> <span>Sequential access</span> </div> </a> <ul id="toc-Sequential_access-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Initial_construction" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Initial_construction"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.5</span> <span>Initial construction</span> </div> </a> <ul id="toc-Initial_construction-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-In_filesystems" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#In_filesystems"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>In filesystems</span> </div> </a> <ul id="toc-In_filesystems-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Performance" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Performance"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Performance</span> </div> </a> <ul id="toc-Performance-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Variations" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Variations"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Variations</span> </div> </a> <button aria-controls="toc-Variations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Variations subsection</span> </button> <ul id="toc-Variations-sublist" class="vector-toc-list"> <li id="toc-Access_concurrency" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Access_concurrency"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.1</span> <span>Access concurrency</span> </div> </a> <ul id="toc-Access_concurrency-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Parallel_algorithms" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Parallel_algorithms"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.2</span> <span>Parallel algorithms</span> </div> </a> <ul id="toc-Parallel_algorithms-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Maple_tree" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Maple_tree"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.3</span> <span>Maple tree</span> </div> </a> <ul id="toc-Maple_tree-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-(a,b)-tree" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#(a,b)-tree"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.4</span> <span>(a,b)-tree</span> </div> </a> <ul id="toc-(a,b)-tree-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">12</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Sources" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Sources"> <div class="vector-toc-text"> <span class="vector-toc-numb">13</span> <span>Sources</span> </div> </a> <button aria-controls="toc-Sources-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Sources subsection</span> </button> <ul id="toc-Sources-sublist" class="vector-toc-list"> <li id="toc-Original_papers" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Original_papers"> <div class="vector-toc-text"> <span class="vector-toc-numb">13.1</span> <span>Original papers</span> </div> </a> <ul id="toc-Original_papers-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">14</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">B-tree</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 33 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-33" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">33 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%B4%D8%AC%D8%B1%D8%A9_%D8%A8%D9%8A" title="شجرة بي – Arabic" lang="ar" hreflang="ar" data-title="شجرة بي" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/B-a%C4%9Fac" title="B-ağac – Azerbaijani" lang="az" hreflang="az" data-title="B-ağac" data-language-autonym="Azərbaycanca" data-language-local-name="Azerbaijani" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Arbre-B" title="Arbre-B – Catalan" lang="ca" hreflang="ca" data-title="Arbre-B" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/B-strom" title="B-strom – Czech" lang="cs" hreflang="cs" data-title="B-strom" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de badge-Q17437798 badge-goodarticle mw-list-item" title="good article badge"><a href="https://de.wikipedia.org/wiki/B-Baum" title="B-Baum – German" lang="de" hreflang="de" data-title="B-Baum" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/%C3%81rbol-B" title="Árbol-B – Spanish" lang="es" hreflang="es" data-title="Árbol-B" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%A8%DB%8C" title="درخت بی – Persian" lang="fa" hreflang="fa" data-title="درخت بی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Arbre_B" title="Arbre B – French" lang="fr" hreflang="fr" data-title="Arbre B" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC" title="B 트리 – Korean" lang="ko" hreflang="ko" data-title="B 트리" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/B-stablo" title="B-stablo – Croatian" lang="hr" hreflang="hr" data-title="B-stablo" data-language-autonym="Hrvatski" data-language-local-name="Croatian" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/B-albero" title="B-albero – Italian" lang="it" hreflang="it" data-title="B-albero" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A2%D7%A5_B" title="עץ B – Hebrew" lang="he" hreflang="he" data-title="עץ B" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-kn mw-list-item"><a href="https://kn.wikipedia.org/wiki/%E0%B2%AC%E0%B2%BF-%E0%B2%9F%E0%B3%8D%E0%B2%B0%E0%B3%80" title="ಬಿ-ಟ್ರೀ – Kannada" lang="kn" hreflang="kn" data-title="ಬಿ-ಟ್ರೀ" data-language-autonym="ಕನ್ನಡ" data-language-local-name="Kannada" class="interlanguage-link-target"><span>ಕನ್ನಡ</span></a></li><li class="interlanguage-link interwiki-la mw-list-item"><a href="https://la.wikipedia.org/wiki/Arbor_B" title="Arbor B – Latin" lang="la" hreflang="la" data-title="Arbor B" data-language-autonym="Latina" data-language-local-name="Latin" class="interlanguage-link-target"><span>Latina</span></a></li><li class="interlanguage-link interwiki-lv mw-list-item"><a href="https://lv.wikipedia.org/wiki/B_koks" title="B koks – Latvian" lang="lv" hreflang="lv" data-title="B koks" data-language-autonym="Latviešu" data-language-local-name="Latvian" class="interlanguage-link-target"><span>Latviešu</span></a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/B-medis" title="B-medis – Lithuanian" lang="lt" hreflang="lt" data-title="B-medis" data-language-autonym="Lietuvių" data-language-local-name="Lithuanian" class="interlanguage-link-target"><span>Lietuvių</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/B-alber" title="B-alber – Lombard" lang="lmo" hreflang="lmo" data-title="B-alber" data-language-autonym="Lombard" data-language-local-name="Lombard" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/B-fa" title="B-fa – Hungarian" lang="hu" hreflang="hu" data-title="B-fa" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-ml mw-list-item"><a href="https://ml.wikipedia.org/wiki/%E0%B4%AC%E0%B4%BF-%E0%B4%9F%E0%B5%8D%E0%B4%B0%E0%B5%80" title="ബി-ട്രീ – Malayalam" lang="ml" hreflang="ml" data-title="ബി-ട്രീ" data-language-autonym="മലയാളം" data-language-local-name="Malayalam" class="interlanguage-link-target"><span>മലയാളം</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/B%E6%9C%A8" title="B木 – Japanese" lang="ja" hreflang="ja" data-title="B木" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/B-tre" title="B-tre – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="B-tre" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/B-drzewo" title="B-drzewo – Polish" lang="pl" hreflang="pl" data-title="B-drzewo" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/%C3%81rvore_B" title="Árvore B – Portuguese" lang="pt" hreflang="pt" data-title="Árvore B" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="B-дерево – Russian" lang="ru" hreflang="ru" data-title="B-дерево" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-ckb mw-list-item"><a href="https://ckb.wikipedia.org/wiki/%D8%AF%D8%B1%DB%95%D8%AE%D8%AA%DB%8C_%D8%A8%DB%8C" title="درەختی بی – Central Kurdish" lang="ckb" hreflang="ckb" data-title="درەختی بی" data-language-autonym="کوردی" data-language-local-name="Central Kurdish" class="interlanguage-link-target"><span>کوردی</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%91-%D1%81%D1%82%D0%B0%D0%B1%D0%BB%D0%BE" title="Б-стабло – Serbian" lang="sr" hreflang="sr" data-title="Б-стабло" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/B-stablo" title="B-stablo – Serbo-Croatian" lang="sh" hreflang="sh" data-title="B-stablo" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/B-tr%C3%A4d" title="B-träd – Swedish" lang="sv" hreflang="sv" data-title="B-träd" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%84%E0%B8%A1%E0%B9%89%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%9A%E0%B8%B5" title="ต้นไม้แบบบี – Thai" lang="th" hreflang="th" data-title="ต้นไม้แบบบี" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%91-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Б-дерево – Ukrainian" lang="uk" hreflang="uk" data-title="Б-дерево" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/B-c%C3%A2y" title="B-cây – Vietnamese" lang="vi" hreflang="vi" data-title="B-cây" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/B-%E6%A8%B9" title="B-樹 – Cantonese" lang="yue" hreflang="yue" data-title="B-樹" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/B%E6%A0%91" title="B树 – Chinese" lang="zh" hreflang="zh" data-title="B树" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q677051#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/B-tree" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:B-tree" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/B-tree"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=B-tree&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=B-tree&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/B-tree"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=B-tree&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=B-tree&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/B-tree" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/B-tree" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=B-tree&oldid=1259002079" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=B-tree&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=B-tree&id=1259002079&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FB-tree"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FB-tree"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=B-tree&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=B-tree&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:B-Trees" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q677051" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">A self-balancing, tree-based data structure, that allows read/write access in logarithmic time</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="/wiki/Binary_tree" title="Binary tree">Binary tree</a> or <a href="/wiki/B%2B_tree" title="B+ tree">B+ tree</a>.</div> <style data-mw-deduplicate="TemplateStyles:r1257001546">.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme) div:not(.notheme){background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table tr{display:table-row!important}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">B-tree</th></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/List_of_data_structures" title="List of data structures">Type</a></th><td class="infobox-data"><a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Tree (data structure)</a></td></tr><tr><th scope="row" class="infobox-label">Invented</th><td class="infobox-data">1970<sup id="cite_ref-bayer-mccreight-1970_1-0" class="reference"><a href="#cite_note-bayer-mccreight-1970-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data"><a href="/wiki/Rudolf_Bayer" title="Rudolf Bayer">Rudolf Bayer</a>, <a href="/wiki/Edward_M._McCreight" title="Edward M. McCreight">Edward M. McCreight</a></td></tr><tr><td colspan="2" class="infobox-full-data"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1257001546"><table class="infobox-subbox infobox-3cols-child infobox-table"><tbody><tr><th colspan="4" class="infobox-header"><a href="/wiki/Time_complexity" title="Time complexity">Time complexity</a> in <a href="/wiki/Big_O_notation" title="Big O notation">big O notation</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Operation</th><td class="infobox-data infobox-data-a"> <b>Average</b></td><td class="infobox-data infobox-data-b"> <b>Worst case</b></td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Search</th><td class="infobox-data infobox-data-a"> O(log <i>n</i>)</td><td class="infobox-data infobox-data-b"> O(log <i>n</i>)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Insert</th><td class="infobox-data infobox-data-a"> O(log <i>n</i>)</td><td class="infobox-data infobox-data-b"> O(log <i>n</i>)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Delete</th><td class="infobox-data infobox-data-a"> O(log <i>n</i>)</td><td class="infobox-data infobox-data-b"> O(log <i>n</i>)</td></tr><tr><th colspan="4" class="infobox-header"><a href="/wiki/Space_complexity" title="Space complexity">Space complexity</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Space</th><td class="infobox-data infobox-data-a"> O(<i>n</i>)</td><td class="infobox-data infobox-data-b"> O(<i>n</i>)</td></tr></tbody></table></td></tr></tbody></table> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, a <b>B-tree</b> is a self-balancing <a href="/wiki/Tree_data_structure" class="mw-redirect" title="Tree data structure">tree data structure</a> that maintains sorted data and allows searches, sequential access, insertions, and deletions in <a href="/wiki/Logarithmic_time" class="mw-redirect" title="Logarithmic time">logarithmic time</a>. The B-tree generalizes the <a href="/wiki/Binary_search_tree" title="Binary search tree">binary search tree</a>, allowing for <a href="/wiki/Node_(computer_science)" title="Node (computer science)">nodes</a> with more than two children.<sup id="cite_ref-FOOTNOTEComer1979_2-0" class="reference"><a href="#cite_note-FOOTNOTEComer1979-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Unlike other <a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">self-balancing binary search trees</a>, the B-tree is well suited for storage systems that read and write relatively large <a href="/wiki/Block_(data_storage)" title="Block (data storage)">blocks of data</a>, such as <a href="/wiki/Database" title="Database">databases</a> and <a href="/wiki/File_system" title="File system">file systems</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="History">History</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=1" title="Edit section: History"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>B-trees were invented by <a href="/wiki/Rudolf_Bayer" title="Rudolf Bayer">Rudolf Bayer</a> and <a href="/wiki/Edward_M._McCreight" title="Edward M. McCreight">Edward M. McCreight</a> while working at <a href="/wiki/Boeing" title="Boeing">Boeing Research Labs</a>, for the purpose of efficiently managing index pages for large random-access files. The basic assumption was that indices would be so voluminous that only small chunks of the tree could fit in main memory. Bayer and McCreight's paper <i>Organization and maintenance of large ordered indices</i><sup id="cite_ref-bayer-mccreight-1970_1-1" class="reference"><a href="#cite_note-bayer-mccreight-1970-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> was first circulated in July 1970 and later published in <i><a href="/wiki/Acta_Informatica" title="Acta Informatica">Acta Informatica</a></i>.<sup id="cite_ref-FOOTNOTEBayerMcCreight1972_3-0" class="reference"><a href="#cite_note-FOOTNOTEBayerMcCreight1972-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>Bayer and McCreight never explained what, if anything, the <i>B</i> stands for; <i>Boeing</i>, <i>balanced</i>, <i>between</i>, <i>broad</i>, <i>bushy</i>, and <i>Bayer</i> have been suggested.<sup id="cite_ref-FOOTNOTEComer1979123_footnote_1_4-0" class="reference"><a href="#cite_note-FOOTNOTEComer1979123_footnote_1-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-herrenalb_5-0" class="reference"><a href="#cite_note-herrenalb-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> McCreight has said that "the more you think about what the B in B-trees means, the better you understand B-trees".<sup id="cite_ref-herrenalb_5-1" class="reference"><a href="#cite_note-herrenalb-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=2" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>According to <a href="/wiki/Donald_Knuth" title="Donald Knuth">Knuth</a>'s definition, a B-tree of order <i>m</i> is a tree which satisfies the following properties:<sup id="cite_ref-FOOTNOTEKnuth1998483_7-0" class="reference"><a href="#cite_note-FOOTNOTEKnuth1998483-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p> <ol><li>Every node has at most <i>m</i> children.</li> <li>Every node, except for the root and the leaves, has at least ⌈<i>m</i>/2⌉ children.</li> <li>The root node has at least two children unless it is a leaf.</li> <li>All leaves appear on the same level.</li> <li>A non-leaf node with <i>k</i> children contains <i>k</i>−1 keys.</li></ol> <p>Each internal node's keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: <i>a</i><sub>1</sub> and <i>a</i><sub>2</sub>. All values in the leftmost subtree will be less than <i>a</i><sub>1</sub>, all values in the middle subtree will be between <i>a</i><sub>1</sub> and <i>a</i><sub>2</sub>, and all values in the rightmost subtree will be greater than <i>a</i><sub>2</sub>. </p> <dl><dt>Internal nodes</dt> <dd>Internal nodes (also known as <a href="/wiki/Tree_(data_structure)#Terminology" class="mw-redirect" title="Tree (data structure)">inner nodes</a>) are all nodes except for leaf nodes and the root node. They are usually represented as an ordered set of elements and child pointers. Every internal node contains a <b>maximum</b> of <i>U</i> children and a <b>minimum</b> of <i>L</i> children. Thus, the number of elements is always 1 less than the number of child pointers (the number of elements is between <i>L</i>−1 and <i>U</i>−1). <i>U</i> must be either 2<i>L</i> or 2<i>L</i>−1; therefore each internal node is at least half full. The relationship between <i>U</i> and <i>L</i> implies that two half-full nodes can be joined to make a legal node, and one full node can be split into two legal nodes (if there's room to push one element up into the parent). These properties make it possible to delete and insert new values into a B-tree and adjust the tree to preserve the B-tree properties.</dd> <dt>The root node</dt> <dd>The root node's number of children has the same upper limit as internal nodes, but has no lower limit. For example, when there are fewer than <i>L</i>−1 elements in the entire tree, the root will be the only node in the tree with no children at all.</dd></dl> <dl><dt>Leaf nodes</dt> <dd>In Knuth's terminology, the "leaf" nodes are the actual data objects / chunks. The internal nodes that are one level above these leaves are what would be called the "leaves" by other authors: these nodes only store keys (at most <i>m</i>-1, and at least <i>m</i>/2-1 if they are not the root) and pointers (one for each key) to nodes carrying the data objects / chunks.</dd></dl> <p>A B-tree of depth <i>n</i>+1 can hold about <i>U</i> times as many items as a B-tree of depth <i>n</i>, but the cost of search, insert, and delete operations grows with the depth of the tree. As with any balanced tree, the cost grows much more slowly than the number of elements. </p><p>Some balanced trees store values only at leaf nodes, and use different kinds of nodes for leaf nodes and internal nodes. B-trees keep values in every node in the tree except leaf nodes. </p> <div class="mw-heading mw-heading3"><h3 id="Differences_in_terminology">Differences in terminology</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=3" title="Edit section: Differences in terminology"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The literature on B-trees is not uniform in its terminology.<sup id="cite_ref-FOOTNOTEFolkZoellick1992362_8-0" class="reference"><a href="#cite_note-FOOTNOTEFolkZoellick1992362-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><p>Bayer and McCreight (1972),<sup id="cite_ref-FOOTNOTEBayerMcCreight1972_3-1" class="reference"><a href="#cite_note-FOOTNOTEBayerMcCreight1972-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Comer (1979),<sup id="cite_ref-FOOTNOTEComer1979_2-1" class="reference"><a href="#cite_note-FOOTNOTEComer1979-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> and others define the <b>order</b> of B-tree as the minimum number of keys in a non-root node. Folk and Zoellick <sup id="cite_ref-FOOTNOTEFolkZoellick1992363_9-0" class="reference"><a href="#cite_note-FOOTNOTEFolkZoellick1992363-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> points out that terminology is ambiguous because the maximum number of keys is not clear. An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys. Knuth (1998) avoids the problem by defining the <b>order</b> to be the maximum number of children (which is one more than the maximum number of keys).<sup id="cite_ref-FOOTNOTEKnuth1998483_7-1" class="reference"><a href="#cite_note-FOOTNOTEKnuth1998483-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p><p>The term <b>leaf</b> is also inconsistent. Bayer and McCreight (1972)<sup id="cite_ref-FOOTNOTEBayerMcCreight1972_3-2" class="reference"><a href="#cite_note-FOOTNOTEBayerMcCreight1972-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> considered the leaf level to be the lowest level of keys, but Knuth considered the leaf level to be one level below the lowest keys.<sup id="cite_ref-FOOTNOTEFolkZoellick1992363_9-1" class="reference"><a href="#cite_note-FOOTNOTEFolkZoellick1992363-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> There are many possible implementation choices. In some designs, the leaves may hold the entire data record; in other designs, the leaves may only hold pointers to the data record. Those choices are not fundamental to the idea of a B-tree.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </p><p>For simplicity, most authors assume there are a fixed number of keys that fit in a node. The basic assumption is the key size is fixed and the node size is fixed. In practice, variable length keys may be employed.<sup id="cite_ref-FOOTNOTEFolkZoellick1992379_11-0" class="reference"><a href="#cite_note-FOOTNOTEFolkZoellick1992379-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Informal_description">Informal description</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=4" title="Edit section: Informal description"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:B-tree.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/65/B-tree.svg/400px-B-tree.svg.png" decoding="async" width="400" height="111" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/65/B-tree.svg/600px-B-tree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/65/B-tree.svg/800px-B-tree.svg.png 2x" data-file-width="831" data-file-height="231" /></a><figcaption>A B-tree (<a href="#CITEREFBayerMcCreight1972">Bayer & McCreight 1972</a>) of order 5 (<a href="#CITEREFKnuth1998">Knuth 1998</a>).</figcaption></figure> <div class="mw-heading mw-heading3"><h3 id="Node_structure">Node structure</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=5" title="Edit section: Node structure"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>As with other trees, B-trees can be represented as a collection of three types of nodes: <i>root</i>, <i>internal</i> (a.k.a. interior), and <i>leaf</i>. </p><p>Note the following variable definitions: </p> <ul><li><i><span class="texhtml mvar" style="font-style:italic;">K</span></i>: Maximum number of potential search keys for each node in a B-tree. (this value is constant over the entire tree).</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pt_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pt_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e123cb2a8cfbd4b6339f5bda675651d61c55403" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.898ex; height:2.343ex;" alt="{\displaystyle pt_{i}}"></span>: The pointer to a child node which starts a sub-tree.</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pr_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pr_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/619b143ca1b969c20154339f47b694c3115f9999" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:3.107ex; height:2.009ex;" alt="{\displaystyle pr_{i}}"></span>: The pointer to a record which stores the data.</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span>: The search key at the zero-based node index <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span>.</li></ul> <p>In B-trees, the following properties are maintained for these nodes: </p> <ul><li>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/13d91731bf4e9bceddd8afde03a9a191f6d36dfa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\textstyle k_{i}}"></span> exists in any node in a B+ tree, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47cf5694daa56b852d661ead6b0ade9c8d282513" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.111ex; height:2.509ex;" alt="{\displaystyle k_{i-1}}"></span> exists in that node where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\geq 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>≥</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i\geq 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a40d31039a220c00dcc836babe2c5f6961c689bf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.063ex; height:2.343ex;" alt="{\displaystyle i\geq 1}"></span>.</li> <li>All leaf nodes have the same number of ancestors (i.e., they are all at the same depth).</li></ul> <p>Each internal node in a B-tree has the following format: </p> <table class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"> <caption>Internal node structure </caption> <tbody><tr> <th>pt<sub>0</sub> </th> <th>k<sub>0</sub> </th> <th>pt<sub>1</sub> </th> <th>pr<sub>0</sub> </th> <th>k<sub>1</sub> </th> <th>pt<sub>2</sub> </th> <th>pr<sub>1</sub> </th> <th>... </th> <th>k<sub>K-1</sub> </th> <th>pt<sub>K</sub> </th> <th>pr<sub>K-1</sub> </th></tr></tbody></table> <table class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"> <caption>Internal node pointer structure </caption> <tbody><tr> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pt_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pt_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e8f50f4d59cce58b802e0e95a40154771efe0387" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:3.153ex; height:2.343ex;" alt="{\displaystyle pt_{0}}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eafdfeca4ead3960fca92311910970eba7ec48a1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.265ex; height:2.509ex;" alt="{\displaystyle k_{0}}"></span> exists </th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pt_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pt_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e123cb2a8cfbd4b6339f5bda675651d61c55403" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.898ex; height:2.343ex;" alt="{\displaystyle pt_{i}}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47cf5694daa56b852d661ead6b0ade9c8d282513" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.111ex; height:2.509ex;" alt="{\displaystyle k_{i-1}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span> exist </th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pt_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pt_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e123cb2a8cfbd4b6339f5bda675651d61c55403" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.898ex; height:2.343ex;" alt="{\displaystyle pt_{i}}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47cf5694daa56b852d661ead6b0ade9c8d282513" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.111ex; height:2.509ex;" alt="{\displaystyle k_{i-1}}"></span> exists, and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span> does not exist </th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pt_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pt_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e123cb2a8cfbd4b6339f5bda675651d61c55403" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.898ex; height:2.343ex;" alt="{\displaystyle pt_{i}}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47cf5694daa56b852d661ead6b0ade9c8d282513" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.111ex; height:2.509ex;" alt="{\displaystyle k_{i-1}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span> do not exist </th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pr_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pr_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/619b143ca1b969c20154339f47b694c3115f9999" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:3.107ex; height:2.009ex;" alt="{\displaystyle pr_{i}}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span> exists </th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pr_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pr_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/619b143ca1b969c20154339f47b694c3115f9999" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:3.107ex; height:2.009ex;" alt="{\displaystyle pr_{i}}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span> does not exist </th></tr> <tr> <td>Points to subtree in which all search keys are less than <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eafdfeca4ead3960fca92311910970eba7ec48a1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.265ex; height:2.509ex;" alt="{\displaystyle k_{0}}"></span>. </td> <td>Points to subtree in which all search keys are greater than <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47cf5694daa56b852d661ead6b0ade9c8d282513" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.111ex; height:2.509ex;" alt="{\displaystyle k_{i-1}}"></span> and are less than <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span>. </td> <td>Points to subtree in which all search keys are greater than <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47cf5694daa56b852d661ead6b0ade9c8d282513" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.111ex; height:2.509ex;" alt="{\displaystyle k_{i-1}}"></span>. </td> <td>Here, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pt_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pt_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e123cb2a8cfbd4b6339f5bda675651d61c55403" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.898ex; height:2.343ex;" alt="{\displaystyle pt_{i}}"></span> is empty. </td> <td>Points to a record with a value equal to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span>. </td> <td>Here, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pr_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pr_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/619b143ca1b969c20154339f47b694c3115f9999" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:3.107ex; height:2.009ex;" alt="{\displaystyle pr_{i}}"></span> is empty. </td></tr></tbody></table> <p>Each leaf node in a B-tree has the following format: </p> <table class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"> <caption>Leaf node structure </caption> <tbody><tr> <th>pr<sub>0</sub> </th> <th>k<sub>0</sub> </th> <th>pr<sub>1</sub> </th> <th>k<sub>1</sub> </th> <th>... </th> <th>pr<sub>K-1</sub> </th> <th>k<sub>K-1</sub> </th></tr></tbody></table> <table class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"> <caption>Leaf node pointer structure </caption> <tbody><tr> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pr_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pr_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/619b143ca1b969c20154339f47b694c3115f9999" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:3.107ex; height:2.009ex;" alt="{\displaystyle pr_{i}}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span> exists </th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pr_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pr_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/619b143ca1b969c20154339f47b694c3115f9999" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:3.107ex; height:2.009ex;" alt="{\displaystyle pr_{i}}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span> does not exist </th></tr> <tr> <td>Points to a record with a value equal to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span>. </td> <td>Here, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle pr_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle pr_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/619b143ca1b969c20154339f47b694c3115f9999" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:3.107ex; height:2.009ex;" alt="{\displaystyle pr_{i}}"></span> is empty. </td></tr></tbody></table> <p>The node bounds are summarized in the table below: </p> <table class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"> <tbody><tr> <th>Node type </th> <th>Min number<br /> of keys </th> <th>Max number<br /> of keys </th> <th>Min number<br /> of child nodes </th> <th>Max number<br /> of child nodes </th></tr> <tr> <td>Root node when it is a leaf node </td> <td>0 </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>K</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b76fce82a62ed5461908f0dc8f037de4e3686b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}"></span> </td> <td>0 </td> <td>0 </td></tr> <tr> <td>Root node when it is an internal node </td> <td>1 </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>K</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b76fce82a62ed5461908f0dc8f037de4e3686b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}"></span> </td> <td>2<sup id="cite_ref-Navathe2_12-0" class="reference"><a href="#cite_note-Navathe2-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>K</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/95e3c16df6a96cbc6bb45ef18a401e161c3dd348" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.069ex; height:2.343ex;" alt="{\displaystyle K+1}"></span> </td></tr> <tr> <td>Internal node </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor K/2\rfloor }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⌊</mo> <mi>K</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo fence="false" stretchy="false">⌋</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lfloor K/2\rfloor }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a41d6e0a2cdb6d381062ef6187c68b79d38293fd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.456ex; height:2.843ex;" alt="{\displaystyle \lfloor K/2\rfloor }"></span> </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>K</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b76fce82a62ed5461908f0dc8f037de4e3686b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}"></span> </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lceil (K+1)/2\rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⌈</mo> <mo stretchy="false">(</mo> <mi>K</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo fence="false" stretchy="false">⌉</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lceil (K+1)/2\rceil }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cfb97164fb1bf3ac415289e270daa94cc0c96d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.268ex; height:2.843ex;" alt="{\displaystyle \lceil (K+1)/2\rceil }"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \equiv \lfloor K/2\rfloor +1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>≡</mo> <mo fence="false" stretchy="false">⌊</mo> <mi>K</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo fence="false" stretchy="false">⌋</mo> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \equiv \lfloor K/2\rfloor +1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f36ed3fd5fac93cbeffcc420a4dd279930f8170d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.912ex; height:2.843ex;" alt="{\displaystyle \equiv \lfloor K/2\rfloor +1}"></span> </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>K</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/95e3c16df6a96cbc6bb45ef18a401e161c3dd348" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.069ex; height:2.343ex;" alt="{\displaystyle K+1}"></span> </td></tr> <tr> <td>Leaf node </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lceil K/2\rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⌈</mo> <mi>K</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo fence="false" stretchy="false">⌉</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lceil K/2\rceil }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/501d568498e139e04bae118058209e936718db2e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.456ex; height:2.843ex;" alt="{\displaystyle \lceil K/2\rceil }"></span> </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>K</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b76fce82a62ed5461908f0dc8f037de4e3686b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}"></span> </td> <td>0 </td> <td>0 </td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Insertion_and_deletion">Insertion and deletion</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=6" title="Edit section: Insertion and deletion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In order to maintain the predefined range of child nodes, internal nodes may be joined or split. </p><p>Usually, the number of keys is chosen to vary between <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d8106478cb4da6af49992eeb3a3b8690d27797ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.378ex; height:2.176ex;" alt="{\displaystyle 2d}"></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span> is the minimum number of keys, and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/056e0c06c828dbe71a0f9021b2828ff176a3d337" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d+1}"></span> is the minimum <a href="/wiki/Outdegree#Indegree_and_outdegree" class="mw-redirect" title="Outdegree">degree</a> or <a href="/wiki/Branching_factor" title="Branching factor">branching factor</a> of the tree. The factor of 2 will guarantee that nodes can be split or combined. </p><p>If an internal node has <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d8106478cb4da6af49992eeb3a3b8690d27797ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.378ex; height:2.176ex;" alt="{\displaystyle 2d}"></span> keys, then adding a key to that node can be accomplished by splitting the hypothetical <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2d+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2d+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d68ab692c5c4a44b63f3bd320249b8cb8d035191" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.381ex; height:2.343ex;" alt="{\displaystyle 2d+1}"></span> key node into two <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span> key nodes and moving the key that would have been in the middle to the parent node. Each split node has the required minimum number of keys. Similarly, if an internal node and its neighbor each have <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span> keys, then a key may be deleted from the internal node by combining it with its neighbor. Deleting the key would make the internal node have <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0195b64ba44bcc80b4c98e9d34256b4043fe519e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}"></span> keys; joining the neighbor would add <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span> keys plus one more key brought down from the neighbor's parent. The result is an entirely full node of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d8106478cb4da6af49992eeb3a3b8690d27797ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.378ex; height:2.176ex;" alt="{\displaystyle 2d}"></span> keys. </p><p>A B-tree is kept balanced after insertion by splitting a would-be overfilled node, of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2d+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2d+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d68ab692c5c4a44b63f3bd320249b8cb8d035191" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.381ex; height:2.343ex;" alt="{\displaystyle 2d+1}"></span> keys, into two <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span>-key siblings and inserting the mid-value key into the parent. Depth only increases when the root is split, maintaining balance. Similarly, a B-tree is kept balanced after deletion by merging or redistributing keys among siblings to maintain the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span>-key minimum for non-root nodes. A merger reduces the number of keys in the parent potentially forcing it to merge or redistribute keys with its siblings, and so on. The only change in depth occurs when the root has two children, of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span> and (transitionally) <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0195b64ba44bcc80b4c98e9d34256b4043fe519e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}"></span> keys, in which case the two siblings and parent are merged, reducing the depth by one. </p><p>This depth will increase slowly as elements are added to the tree, but an increase in the overall depth is infrequent, and results in all leaf nodes being one more node farther away from the root. </p> <div class="mw-heading mw-heading3"><h3 id="Comparison_to_other_trees">Comparison to other trees</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=7" title="Edit section: Comparison to other trees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full. </p><p>B-trees have substantial advantages over alternative implementations when the time to access the data of a node greatly exceeds the time spent processing that data, because then the cost of accessing the node may be amortized over multiple operations within the node. This usually occurs when the node data are in <a href="/wiki/Secondary_storage" class="mw-redirect" title="Secondary storage">secondary storage</a> such as <a href="/wiki/Hard_drive" class="mw-redirect" title="Hard drive">disk drives</a>. By maximizing the number of keys within each <a href="/wiki/Internal_node" class="mw-redirect" title="Internal node">internal node</a>, the height of the tree decreases and the number of expensive node accesses is reduced. In addition, rebalancing of the tree occurs less often. The maximum number of child nodes depends on the information that must be stored for each child node and the size of a full <a href="/wiki/Block_(data_storage)" title="Block (data storage)">disk block</a> or an analogous size in secondary storage. While 2–3 B-trees are easier to explain, practical B-trees using secondary storage need a large number of child nodes to improve performance. </p> <div class="mw-heading mw-heading3"><h3 id="Variants">Variants</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=8" title="Edit section: Variants"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The term <b>B-tree</b> may refer to a specific design or it may refer to a general class of designs. In the narrow sense, a B-tree stores keys in its internal nodes but need not store those keys in the records at the leaves. The general class includes variations such as the <a href="/wiki/B%2B_tree" title="B+ tree">B+ tree</a>, the B<sup>*</sup> tree and the B<sup>*+</sup> tree. </p> <ul><li>In the <a href="/wiki/B%2B_tree" title="B+ tree">B+ tree</a>, the internal nodes do not store any pointers to records, thus all pointers to records are stored in the leaf nodes. In addition, a leaf node may include a pointer to the next leaf node to speed up sequential access.<sup id="cite_ref-FOOTNOTEComer1979_2-2" class="reference"><a href="#cite_note-FOOTNOTEComer1979-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Because B+ tree internal nodes have fewer pointers, each node can hold more keys, causing the tree to be shallower, and thus, faster to search.</li> <li>The B<sup>*</sup> tree balances more neighboring internal nodes to keep the internal nodes more densely packed.<sup id="cite_ref-FOOTNOTEComer1979_2-3" class="reference"><a href="#cite_note-FOOTNOTEComer1979-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> This variant ensures non-root nodes are at least 2/3 full instead of 1/2.<sup id="cite_ref-FOOTNOTEKnuth1998488_13-0" class="reference"><a href="#cite_note-FOOTNOTEKnuth1998488-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> As the most costly part of operation of inserting the node in B-tree is splitting the node, B<sup>*</sup>-trees are created to postpone splitting operation as long as they can.<sup id="cite_ref-Milo_14-0" class="reference"><a href="#cite_note-Milo-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with a node next to it. This spill operation is less costly to do than split, because it requires only shifting the keys between existing nodes, not allocating memory for a new one.<sup id="cite_ref-Milo_14-1" class="reference"><a href="#cite_note-Milo-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> For inserting, first it is checked whether the node has some free space in it, and if so, the new key is just inserted in the node. However, if the node is full (it has <span class="texhtml"><i>m</i> − 1</span> keys, where <span class="texhtml mvar" style="font-style:italic;"> m</span> is the order of the tree as maximum number of pointers to subtrees from one node), it needs to be checked whether the right sibling exists and has some free space. If the right sibling has <span class="texhtml"><i>j</i> < <i>m</i> − 1</span> keys, then keys are redistributed between the two sibling nodes as evenly as possible. For this purpose, <span class="texhtml mvar" style="font-style:italic;"><i>m</i> - 1</span> keys from the current node, the new key inserted, one key from the parent node and <span class="texhtml mvar" style="font-style:italic;">j</span> keys from the sibling node are seen as an ordered array of <span class="texhtml"><i>m</i> + <i>j</i> + 1</span> keys. The array becomes split by half, so that <span class="texhtml"><span style="font-size:1em">⌊</span>(<i>m</i> + <i>j</i> + 1)/2<span style="font-size:1em">⌋</span></span> lowest keys stay in the current node, the next (middle) key is inserted in the parent and the rest go to the right sibling.<sup id="cite_ref-Milo_14-2" class="reference"><a href="#cite_note-Milo-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> (The newly inserted key might end up in any of the three places.) The situation when right sibling is full, and left isn't is analogous.<sup id="cite_ref-Milo_14-3" class="reference"><a href="#cite_note-Milo-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> When both the sibling nodes are full, then the two nodes (current node and a sibling) are split into three and one more key is shifted up the tree, to the parent node.<sup id="cite_ref-Milo_14-4" class="reference"><a href="#cite_note-Milo-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> If the parent is full, then spill/split operation propagates towards the root node.<sup id="cite_ref-Milo_14-5" class="reference"><a href="#cite_note-Milo-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> Deleting nodes is somewhat more complex than inserting however.</li> <li>The B<sup>*+</sup> tree combines the main <a href="/wiki/B%2B_tree" title="B+ tree">B+ tree</a> and B<sup>*</sup> tree features together.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup></li> <li>B-trees can be turned into <a href="/wiki/Order_statistic_tree" title="Order statistic tree">order statistic trees</a> to allow rapid searches for the Nth record in key order, or counting the number of records between any two records, and various other related operations.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup></li></ul> <div class="mw-heading mw-heading2"><h2 id="B-tree_usage_in_databases">B-tree usage in databases</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=9" title="Edit section: B-tree usage in databases"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-Tone plainlinks metadata ambox ambox-style ambox-Tone" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section's <b>tone or style may not reflect the <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">encyclopedic tone</a> used on Wikipedia</b>.<span class="hide-when-compact"> See Wikipedia's <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">guide to writing better articles</a> for suggestions.</span> <span class="date-container"><i>(<span class="date">May 2022</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Time_to_search_a_sorted_file">Time to search a sorted file</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=10" title="Edit section: Time to search a sorted file"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Sorting and searching algorithms can be characterized by the number of comparison operations that must be performed using <a href="/wiki/Big_O_notation" title="Big O notation">order notation</a>. A <a href="/wiki/Binary_search" title="Binary search">binary search</a> of a sorted table with <span class="texhtml mvar" style="font-style:italic;">N</span> records, for example, can be done in roughly <span class="texhtml">⌈ log<sub>2</sub> <i>N</i> ⌉</span> comparisons. If the table had 1,000,000 records, then a specific record could be located with at most 20 comparisons: <span class="texhtml">⌈ log<sub>2</sub> (1,000,000) ⌉ = 20</span>. </p><p>Large databases have historically been kept on disk drives. The time to read a record on a disk drive far exceeds the time needed to compare keys once the record is available due to <a href="/wiki/Seek_time" class="mw-redirect" title="Seek time">seek time</a> and a rotational delay. The seek time may be 0 to 20 or more milliseconds, and the rotational delay averages about half the rotation period. For a 7200 RPM drive, the rotation period is 8.33 milliseconds. For a drive such as the Seagate ST3500320NS, the track-to-track seek time is 0.8 milliseconds and the average reading seek time is 8.5 milliseconds.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> For simplicity, assume reading from disk takes about 10 milliseconds. </p><p>The time to locate one record out of a million in the example above would take 20 disk reads times 10 milliseconds per disk read, which is 0.2 seconds. </p><p>The search time is reduced because individual records are grouped together in a disk <b>block</b>. A disk block might be 16 kilobytes. If each record is 160 bytes, then 100 records could be stored in each block. The disk read time above was actually for an entire block. Once the disk head is in position, one or more disk blocks can be read with little delay. With 100 records per block, the last 6 or so comparisons don't need to do any disk reads—the comparisons are all within the last disk block read. </p><p>To speed up the search further, the time to do the first 13 to 14 comparisons (which each required a disk access) must be reduced. </p> <div class="mw-heading mw-heading3"><h3 id="An_index_speeds_the_search">An index speeds the search</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=11" title="Edit section: An index speeds the search"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A B-tree <a href="/wiki/Database_index" title="Database index">index</a> can be used to improve performance. A B-tree index creates a multi-level tree structure that breaks a database down into fixed-size blocks or pages. Each level of this tree can be used to link those pages via an address location, allowing one page (known as a node, or internal page) to refer to another with leaf pages at the lowest level. One page is typically the starting point of the tree, or the "root". This is where the search for a particular key would begin, traversing a path that terminates in a leaf. Most pages in this structure will be leaf pages which refer to specific table rows. </p><p>Because each node (or internal page) can have more than two children, a B-tree index will usually have a shorter height (the distance from the root to the farthest leaf) than a Binary Search Tree. In the example above, initial disk reads narrowed the search range by a factor of two. That can be improved by creating an auxiliary index that contains the first record in each disk block (sometimes called a <a href="/wiki/Database_index#Sparse_index" title="Database index">sparse index</a>). This auxiliary index would be 1% of the size of the original database, but it can be searched quickly. Finding an entry in the auxiliary index would tell us which block to search in the main database; after searching the auxiliary index, we would have to search only that one block of the main database—at a cost of one more disk read. </p><p>In the above example the index would hold 10,000 entries and would take at most 14 comparisons to return a result. Like the main database, the last six or so comparisons in the auxiliary index would be on the same disk block. The index could be searched in about eight disk reads, and the desired record could be accessed in 9 disk reads. </p><p>Creating an auxiliary index can be repeated to make an auxiliary index to the auxiliary index. That would make an aux-aux index that would need only 100 entries and would fit in one disk block. </p><p>Instead of reading 14 disk blocks to find the desired record, we only need to read 3 blocks. This blocking is the core idea behind the creation of the B-tree, where the disk blocks fill-out a hierarchy of levels to make up the index. Reading and searching the first (and only) block of the aux-aux index which is the root of the tree identifies the relevant block in aux-index in the level below. Reading and searching that aux-index block identifies the relevant block to read, until the final level, known as the leaf level, identifies a record in the main database. Instead of 150 milliseconds, we need only 30 milliseconds to get the record. </p><p>The auxiliary indices have turned the search problem from a binary search requiring roughly <span class="texhtml">log<sub>2</sub> <i>N</i></span> disk reads to one requiring only <span class="texhtml">log<sub><i>b</i></sub> <i>N</i></span> disk reads where <span class="texhtml mvar" style="font-style:italic;">b</span> is the blocking factor (the number of entries per block: <span class="texhtml"><i>b</i> = 100</span> entries per block in our example; <span class="texhtml">log<sub>100</sub> 1,000,000 = 3</span> reads). </p><p>In practice, if the main database is being frequently searched, the aux-aux index and much of the aux index may reside in a <a href="/wiki/Page_cache" title="Page cache">disk cache</a>, so they would not incur a disk read. The B-tree remains the standard index implementation in almost all <a href="/wiki/Relational_database" title="Relational database">relational databases</a>, and many nonrelational databases use them too.<sup id="cite_ref-kleppmann_2017_18-0" class="reference"><a href="#cite_note-kleppmann_2017-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Insertions_and_deletions">Insertions and deletions</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=12" title="Edit section: Insertions and deletions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>If the <a href="/wiki/Database" title="Database">database</a> does not change, then compiling the index is simple to do, and the index need never be changed. If there are changes, managing the database and its index require additional computation. </p><p>Deleting records from a database is relatively easy. The index can stay the same, and the record can just be marked as deleted. The database remains in sorted order. If there are a large number of <a href="/wiki/Lazy_deletion" title="Lazy deletion">lazy deletions</a>, then searching and storage become less efficient.<sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> </p><p>Insertions can be very slow in a sorted sequential file because room for the inserted record must be made. Inserting a record before the first record requires shifting all of the records down one. Such an operation is just too expensive to be practical. One solution is to leave some spaces. Instead of densely packing all the records in a block, the block can have some free space to allow for subsequent insertions. Those spaces would be marked as if they were "deleted" records. </p><p>Both insertions and deletions are fast as long as space is available on a block. If an insertion won't fit on the block, then some free space on some nearby block must be found and the auxiliary indices adjusted. The best case is that enough space is available nearby so that the amount of block reorganization can be minimized. Alternatively, some out-of-sequence disk blocks may be used.<sup id="cite_ref-kleppmann_2017_18-1" class="reference"><a href="#cite_note-kleppmann_2017-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Advantages_of_B-tree_usage_for_databases">Advantages of B-tree usage for databases</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=13" title="Edit section: Advantages of B-tree usage for databases"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The B-tree uses all of the ideas described above. In particular, a B-tree: </p> <ul><li>keeps keys in sorted order for sequential traversing</li> <li>uses a hierarchical index to minimize the number of disk reads</li> <li>uses partially full blocks to speed up insertions and deletions</li> <li>keeps the index balanced with a recursive algorithm</li></ul> <p>In addition, a B-tree minimizes waste by making sure the interior nodes are at least half full. A B-tree can handle an arbitrary number of insertions and deletions.<sup id="cite_ref-kleppmann_2017_18-2" class="reference"><a href="#cite_note-kleppmann_2017-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Best_case_and_worst_case_heights">Best case and worst case heights</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=14" title="Edit section: Best case and worst case heights"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Let <span class="nowrap"><i>h</i> ≥ –1</span> be the height of the classic B-tree (see <a href="/wiki/Tree_(data_structure)#Terminology" class="mw-redirect" title="Tree (data structure)">Tree (data structure) § Terminology</a> for the tree height definition). Let <span class="nowrap"><i>n</i> ≥ 0</span> be the number of entries in the tree. Let <i>m</i> be the maximum number of children a node can have. Each node can have at most <span class="nowrap"><i>m</i>−1</span> keys. </p><p>It can be shown (by induction for example) that a B-tree of height <i>h</i> with all its nodes completely filled has <span class="nowrap"><i>n</i> = <i>m</i><sup><i>h</i>+1</sup>–1</span> entries. Hence, the best case height (i.e. the minimum height) of a B-tree is: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\mathrm {min} }=\lceil \log _{m}(n+1)\rceil -1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>h</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">m</mi> <mi mathvariant="normal">i</mi> <mi mathvariant="normal">n</mi> </mrow> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">⌈</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">⌉</mo> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h_{\mathrm {min} }=\lceil \log _{m}(n+1)\rceil -1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/51f6c5fef28784ce50bfed9817aa26c6d6b95a81" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.331ex; height:2.843ex;" alt="{\displaystyle h_{\mathrm {min} }=\lceil \log _{m}(n+1)\rceil -1}"></span></dd></dl> <p>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span> be the minimum number of children an internal (non-root) node must have. For an ordinary B-tree, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=\left\lceil m/2\right\rceil .}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo>=</mo> <mrow> <mo>⌈</mo> <mrow> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> <mo>⌉</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d=\left\lceil m/2\right\rceil .}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6e5b8e6ed38798e4293201ecab0d846b3f93e6ee" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.778ex; height:2.843ex;" alt="{\displaystyle d=\left\lceil m/2\right\rceil .}"></span> </p><p>Comer (1979) and Cormen et al. (2001) give the worst case height (the maximum height) of a B-tree as<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\mathrm {max} }=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\rfloor .}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>h</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">m</mi> <mi mathvariant="normal">a</mi> <mi mathvariant="normal">x</mi> </mrow> </mrow> </msub> <mo>=</mo> <mrow> <mo>⌊</mo> <mrow> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msub> <mo>⁡</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mrow> </mrow> <mo>⌋</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h_{\mathrm {max} }=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\rfloor .}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/75b85818571b143cfecc08e70ccabeed6fee337e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:22.157ex; height:6.176ex;" alt="{\displaystyle h_{\mathrm {max} }=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\rfloor .}"></span></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=15" title="Edit section: Algorithms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Confusing plainlinks metadata ambox ambox-style ambox-confusing" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>may be <a href="/wiki/Wikipedia:Vagueness" title="Wikipedia:Vagueness">confusing or unclear</a> to readers</b>. In particular, the discussion below uses "element", "value", "key", "separator", and "separation value" to mean essentially the same thing. The terms are not clearly defined. There are some subtle issues at the root and leaves.<span class="hide-when-compact"> Please help <a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify">clarify the article</a>. There might be a discussion about this on <a href="/wiki/Talk:B-tree" title="Talk:B-tree">the talk page</a>.</span> <span class="date-container"><i>(<span class="date">February 2012</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Search">Search</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=16" title="Edit section: Search"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Searching is similar to searching a binary search tree. Starting at the root, the tree is recursively traversed from top to bottom. At each level, the search reduces its field of view to the child pointer (subtree) whose range includes the search value. A subtree's range is defined by the values, or keys, contained in its parent node. These limiting values are also known as separation values. </p><p><a href="/wiki/Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">Binary search</a> is typically (but not necessarily) used within nodes to find the separation values and child tree of interest. </p> <div class="mw-heading mw-heading3"><h3 id="Insertion">Insertion</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=17" title="Edit section: Insertion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:B_tree_insertion_example.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/3/33/B_tree_insertion_example.png" decoding="async" width="180" height="391" class="mw-file-element" data-file-width="180" data-file-height="391" /></a><figcaption>A B-tree insertion example with each iteration. The nodes of this B-tree have at most 3 children (Knuth order 3).</figcaption></figure> <p>All insertions start at a leaf node. To insert a new element, search the tree to find the leaf node where the new element should be added. Insert the new element into that node with the following steps: </p> <ol><li>If the node contains fewer than the maximum allowed number of elements, then there is room for the new element. Insert the new element in the node, keeping the node's elements ordered.</li> <li>Otherwise the node is full, evenly split it into two nodes so: <ol><li>A single median is chosen from among the leaf's elements and the new element that is being inserted.</li> <li>Values less than the median are put in the new left node and values greater than the median are put in the new right node, with the median acting as a separation value.</li> <li>The separation value is inserted in the node's parent, which may cause it to be split, and so on. If the node has no parent (i.e., the node was the root), create a new root above this node (increasing the height of the tree).</li></ol></li></ol> <p>If the splitting goes all the way up to the root, it creates a new root with a single separator value and two children, which is why the lower bound on the size of internal nodes does not apply to the root. The maximum number of elements per node is <i>U</i>−1. When a node is split, one element moves to the parent, but one element is added. So, it must be possible to divide the maximum number <i>U</i>−1 of elements into two legal nodes. If this number is odd, then <i>U</i>=2<i>L</i> and one of the new nodes contains (<i>U</i>−2)/2 = <i>L</i>−1 elements, and hence is a legal node, and the other contains one more element, and hence it is legal too. If <i>U</i>−1 is even, then <i>U</i>=2<i>L</i>−1, so there are 2<i>L</i>−2 elements in the node. Half of this number is <i>L</i>−1, which is the minimum number of elements allowed per node. </p><p>An alternative algorithm supports a single pass down the tree from the root to the node where the insertion will take place, splitting any full nodes encountered on the way pre-emptively. This prevents the need to recall the parent nodes into memory, which may be expensive if the nodes are on secondary storage. However, to use this algorithm, we must be able to send one element to the parent and split the remaining <i>U</i>−2 elements into two legal nodes, without adding a new element. This requires <i>U</i> = 2<i>L</i> rather than <i>U</i> = 2<i>L</i>−1, which accounts for why some<sup class="noprint Inline-Template" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Avoid_weasel_words" class="mw-redirect" title="Wikipedia:Avoid weasel words"><span title="The material near this tag possibly uses too vague attribution or weasel words. (September 2019)">which?</span></a></i>]</sup> textbooks impose this requirement in defining B-trees. </p> <div class="mw-heading mw-heading3"><h3 id="Deletion">Deletion</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=18" title="Edit section: Deletion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are two popular strategies for deletion from a B-tree. </p> <ol><li>Locate and delete the item, then restructure the tree to retain its invariants, <b>OR</b></li> <li>Do a single pass down the tree, but before entering (visiting) a node, restructure the tree so that once the key to be deleted is encountered, it can be deleted without triggering the need for any further restructuring</li></ol> <p>The algorithm below uses the former strategy. </p><p>There are two special cases to consider when deleting an element: </p> <ol><li>The element in an internal node is a separator for its child nodes</li> <li>Deleting an element may put its node under the minimum number of elements and children</li></ol> <p>The procedures for these cases are in order below. </p> <div class="mw-heading mw-heading4"><h4 id="Deletion_from_a_leaf_node">Deletion from a leaf node</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=19" title="Edit section: Deletion from a leaf node"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ol><li>Search for the value to delete.</li> <li>If the value is in a leaf node, simply delete it from the node.</li> <li>If underflow happens, rebalance the tree as described in section "Rebalancing after deletion" below.</li></ol> <div class="mw-heading mw-heading4"><h4 id="Deletion_from_an_internal_node">Deletion from an internal node</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=20" title="Edit section: Deletion from an internal node"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Each element in an internal node acts as a separation value for two subtrees, therefore we need to find a replacement for separation. Note that the largest element in the left subtree is still less than the separator. Likewise, the smallest element in the right subtree is still greater than the separator. Both of those elements are in leaf nodes, and either one can be the new separator for the two subtrees. Algorithmically described below: </p> <ol><li>Choose a new separator (either the largest element in the left subtree or the smallest element in the right subtree), remove it from the leaf node it is in, and replace the element to be deleted with the new separator.</li> <li>The previous step deleted an element (the new separator) from a leaf node. If that leaf node is now deficient (has fewer than the required number of nodes), then rebalance the tree starting from the leaf node.</li></ol> <div class="mw-heading mw-heading4"><h4 id="Rebalancing_after_deletion">Rebalancing after deletion</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=21" title="Edit section: Rebalancing after deletion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Rebalancing starts from a leaf and proceeds toward the root until the tree is balanced. If deleting an element from a node has brought it under the minimum size, then some elements must be redistributed to bring all nodes up to the minimum. Usually, the redistribution involves moving an element from a sibling node that has more than the minimum number of nodes. That redistribution operation is called a <b>rotation</b>. If no sibling can spare an element, then the deficient node must be <b>merged</b> with a sibling. The merge causes the parent to lose a separator element, so the parent may become deficient and need rebalancing. The merging and rebalancing may continue all the way to the root. Since the minimum element count doesn't apply to the root, making the root be the only deficient node is not a problem. The algorithm to rebalance the tree is as follows: </p> <ul><li>If the deficient node's right sibling exists and has more than the minimum number of elements, then rotate left <ol><li>Copy the separator from the parent to the end of the deficient node (the separator moves down; the deficient node now has the minimum number of elements)</li> <li>Replace the separator in the parent with the first element of the right sibling (right sibling loses one node but still has at least the minimum number of elements)</li> <li>The tree is now balanced</li></ol></li> <li>Otherwise, if the deficient node's left sibling exists and has more than the minimum number of elements, then rotate right <ol><li>Copy the separator from the parent to the start of the deficient node (the separator moves down; deficient node now has the minimum number of elements)</li> <li>Replace the separator in the parent with the last element of the left sibling (left sibling loses one node but still has at least the minimum number of elements)</li> <li>The tree is now balanced</li></ol></li> <li>Otherwise, if both immediate siblings have only the minimum number of elements, then merge with a sibling sandwiching their separator taken off from their parent <ol><li>Copy the separator to the end of the left node (the left node may be the deficient node or it may be the sibling with the minimum number of elements)</li> <li>Move all elements from the right node to the left node (the left node now has the maximum number of elements, and the right node – empty)</li> <li>Remove the separator from the parent along with its empty right child (the parent loses an element) <ul><li>If the parent is the root and now has no elements, then free it and make the merged node the new root (tree becomes shallower)</li> <li>Otherwise, if the parent has fewer than the required number of elements, then rebalance the parent<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup></li></ul></li></ol></li></ul> <dl><dd><small><b>Note</b>: The rebalancing operations are different for B+ trees (e.g., rotation is different because parent has copy of the key) and B<sup>*</sup>-tree (e.g., three siblings are merged into two siblings).</small></dd></dl> <div class="mw-heading mw-heading3"><h3 id="Sequential_access">Sequential access</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=22" title="Edit section: Sequential access"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>While freshly loaded databases tend to have good sequential behaviour, this behaviour becomes increasingly difficult to maintain as a database grows, resulting in more random I/O and performance challenges.<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Initial_construction">Initial construction</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=23" title="Edit section: Initial construction"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Unreferenced_section plainlinks metadata ambox ambox-content ambox-Unreferenced" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>does not <a href="/wiki/Wikipedia:Citing_sources" title="Wikipedia:Citing sources">cite</a> any <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">sources</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/B-tree" title="Special:EditPage/B-tree">improve this section</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and <a href="/wiki/Wikipedia:Verifiability#Burden_of_evidence" title="Wikipedia:Verifiability">removed</a>.</span> <span class="date-container"><i>(<span class="date">April 2018</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>A common special case is adding a large amount of <i>pre-sorted</i> data into an initially empty B-tree. While it is quite possible to simply perform a series of successive inserts, inserting sorted data results in a tree composed almost entirely of half-full nodes. Instead, a special "bulk loading" <a href="/wiki/Algorithm" title="Algorithm">algorithm</a> can be used to produce a more efficient tree with a higher branching factor. </p><p>When the input is sorted, all insertions are at the rightmost edge of the tree, and in particular any time a node is split, we are guaranteed that no more insertions will take place in the left half. When bulk loading, we take advantage of this, and instead of splitting overfull nodes evenly, split them as <i>unevenly</i> as possible: leave the left node completely full and create a right node with zero keys and one child (in violation of the usual B-tree rules). </p><p>At the end of bulk loading, the tree is composed almost entirely of completely full nodes; only the rightmost node on each level may be less than full. Because those nodes may also be less than <i>half</i> full, to re-establish the normal B-tree rules, combine such nodes with their (guaranteed full) left siblings and divide the keys to produce two nodes at least half full. The only node which lacks a full left sibling is the root, which is permitted to be less than half full. </p> <div class="mw-heading mw-heading2"><h2 id="In_filesystems">In filesystems</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=24" title="Edit section: In filesystems"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In addition to its use in databases, the B-tree (or <a href="#Variants">§ Variants</a>) is also used in filesystems to allow quick random access to an arbitrary block in a particular file. The basic problem is turning the file block <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> address into a disk block address. </p><p>Some operating systems require the user to allocate the maximum size of the file when the file is created. The file can then be allocated as contiguous disk blocks. In that case, to convert the file block address <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> into a disk block address, the operating system simply adds the file block address <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> to the address of the first disk block constituting the file. The scheme is simple, but the file cannot exceed its created size. </p><p>Other operating systems allow a file to grow. The resulting disk blocks may not be contiguous, so mapping logical blocks to physical blocks is more involved. </p><p><a href="/wiki/MS-DOS" title="MS-DOS">MS-DOS</a>, for example, used a simple <a href="/wiki/File_Allocation_Table" title="File Allocation Table">File Allocation Table</a> (FAT). The FAT has an entry for each disk block,<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>note 1<span class="cite-bracket">]</span></a></sup> and that entry identifies whether its block is used by a file and if so, which block (if any) is the next disk block of the same file. So, the allocation of each file is represented as a <a href="/wiki/Linked_list" title="Linked list">linked list</a> in the table. In order to find the disk address of file block <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span>, the operating system (or disk utility) must sequentially follow the file's linked list in the FAT. Worse, to find a free disk block, it must sequentially scan the FAT. For MS-DOS, that was not a huge penalty because the disks and files were small and the FAT had few entries and relatively short file chains. In the <a href="/wiki/FAT12" class="mw-redirect" title="FAT12">FAT12</a> filesystem (used on floppy disks and early hard disks), there were no more than 4,080 <sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>note 2<span class="cite-bracket">]</span></a></sup> entries, and the FAT would usually be resident in memory. As disks got bigger, the FAT architecture began to confront penalties. On a large disk using FAT, it may be necessary to perform disk reads to learn the disk location of a file block to be read or written. </p><p><a href="/wiki/TOPS-20" title="TOPS-20">TOPS-20</a> (and possibly <a href="/wiki/TENEX_(operating_system)" title="TENEX (operating system)">TENEX</a>) used a 0 to 2 level tree that has similarities to a B-tree<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (October 2009)">citation needed</span></a></i>]</sup>. A disk block was 512 36-bit words. If the file fit in a 512 (2<sup>9</sup>) word block, then the file directory would point to that physical disk block. If the file fit in 2<sup>18</sup> words, then the directory would point to an aux index; the 512 words of that index would either be NULL (the block isn't allocated) or point to the physical address of the block. If the file fit in 2<sup>27</sup> words, then the directory would point to a block holding an aux-aux index; each entry would either be NULL or point to an aux index. Consequently, the physical disk block for a 2<sup>27</sup> word file could be located in two disk reads and read on the third. </p><p>Apple's filesystem <a href="/wiki/HFS%2B" class="mw-redirect" title="HFS+">HFS+</a> and <a href="/wiki/APFS" class="mw-redirect" title="APFS">APFS</a>, Microsoft's <a href="/wiki/NTFS" title="NTFS">NTFS</a>,<sup id="cite_ref-insidewin2kntfs_25-0" class="reference"><a href="#cite_note-insidewin2kntfs-25"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> AIX (jfs2) and some <a href="/wiki/Linux" title="Linux">Linux</a> filesystems, such as <a href="/wiki/Bcachefs" title="Bcachefs">Bcachefs</a>, <a href="/wiki/Btrfs" title="Btrfs">Btrfs</a> and <a href="/wiki/Ext4" title="Ext4">ext4</a>, use B-trees. </p><p>B<sup>*</sup>-trees are used in the <a href="/wiki/Hierarchical_File_System_(Apple)" title="Hierarchical File System (Apple)">HFS</a> and <a href="/wiki/Reiser4" title="Reiser4">Reiser4</a> <a href="/wiki/File_system" title="File system">file systems</a>. </p><p><a href="/wiki/DragonFly_BSD" title="DragonFly BSD">DragonFly BSD</a>'s <a href="/wiki/HAMMER_(file_system)" title="HAMMER (file system)">HAMMER</a> file system uses a modified B+-tree.<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Performance">Performance</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=25" title="Edit section: Performance"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Unreferenced_section plainlinks metadata ambox ambox-content ambox-Unreferenced" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>does not <a href="/wiki/Wikipedia:Citing_sources" title="Wikipedia:Citing sources">cite</a> any <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">sources</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/B-tree" title="Special:EditPage/B-tree">improve this section</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and <a href="/wiki/Wikipedia:Verifiability#Burden_of_evidence" title="Wikipedia:Verifiability">removed</a>.</span> <span class="date-container"><i>(<span class="date">May 2020</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>A B-tree grows slower with growing data amount, than the linearity of a linked list. Compared to a <a href="/wiki/Skip_list" title="Skip list">skip list</a>, both structures have the same performance, but the B-tree scales better for growing <i>n</i>. A <a href="/wiki/T-tree" title="T-tree">T-tree</a>, for <a href="/wiki/Main_memory_database" class="mw-redirect" title="Main memory database">main memory database</a> systems, is similar but more compact. </p> <div class="mw-heading mw-heading2"><h2 id="Variations">Variations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=26" title="Edit section: Variations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Access_concurrency">Access concurrency</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=27" title="Edit section: Access concurrency"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Lehman and Yao<sup id="cite_ref-27" class="reference"><a href="#cite_note-27"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> showed that all the read locks could be avoided (and thus concurrent access greatly improved) by linking the tree blocks at each level together with a "next" pointer. This results in a tree structure where both insertion and search operations descend from the root to the leaf. Write locks are only required as a tree block is modified. This maximizes access concurrency by multiple users, an important consideration for databases and/or other B-tree-based <a href="/wiki/ISAM" title="ISAM">ISAM</a> storage methods. The cost associated with this improvement is that empty pages cannot be removed from the btree during normal operations. (However, see <sup id="cite_ref-28" class="reference"><a href="#cite_note-28"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup> for various strategies to implement node merging, and source code at.<sup id="cite_ref-29" class="reference"><a href="#cite_note-29"><span class="cite-bracket">[</span>27<span class="cite-bracket">]</span></a></sup>) </p><p>United States Patent 5283894, granted in 1994, appears to show a way to use a 'Meta Access Method' <sup id="cite_ref-30" class="reference"><a href="#cite_note-30"><span class="cite-bracket">[</span>28<span class="cite-bracket">]</span></a></sup> to allow concurrent B+ tree access and modification without locks. The technique accesses the tree 'upwards' for both searches and updates by means of additional in-memory indexes that point at the blocks in each level in the block cache. No reorganization for deletes is needed and there are no 'next' pointers in each block as in Lehman and Yao. </p> <div class="mw-heading mw-heading3"><h3 id="Parallel_algorithms">Parallel algorithms</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=28" title="Edit section: Parallel algorithms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Since B-trees are similar in structure to <a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">red-black trees</a>, <a href="/wiki/Red%E2%80%93black_tree#Parallel_algorithms" title="Red–black tree">parallel algorithms for red-black trees</a> can be applied to B-trees as well. </p> <div class="mw-heading mw-heading3"><h3 id="Maple_tree">Maple tree</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=29" title="Edit section: Maple tree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A Maple tree is a B-tree developed for use in the <a href="/wiki/Linux_kernel" title="Linux kernel">Linux kernel</a> to reduce lock contention in virtual memory management.<sup id="cite_ref-31" class="reference"><a href="#cite_note-31"><span class="cite-bracket">[</span>29<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-32" class="reference"><a href="#cite_note-32"><span class="cite-bracket">[</span>30<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-33" class="reference"><a href="#cite_note-33"><span class="cite-bracket">[</span>31<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="(a,b)-tree"><span id=".28a.2Cb.29-tree"></span>(a,b)-tree</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=30" title="Edit section: (a,b)-tree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>(a,b)-trees are generalizations of B-trees. B-trees require that each internal node have a minimum of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor K/2\rfloor +1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⌊</mo> <mi>K</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo fence="false" stretchy="false">⌋</mo> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lfloor K/2\rfloor +1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/65c724cd2c988717d5dcec74b1b793ea0af15b9f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.458ex; height:2.843ex;" alt="{\displaystyle \lfloor K/2\rfloor +1}"></span> children and a maximum of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>K</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b76fce82a62ed5461908f0dc8f037de4e3686b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}"></span> children, for some preset value of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>K</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b76fce82a62ed5461908f0dc8f037de4e3686b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}"></span>. In contrast, an (a,b)-tree allows the minimum number of children for an internal node to be set arbitrarily low. In an (a,b)-tree, each internal node has between <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> children, for some preset values of <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span>. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=31" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/B%2B_tree" title="B+ tree">B+ tree</a></li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a></li> <li><a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li> <li><a href="/wiki/2%E2%80%933_tree" title="2–3 tree">2–3 tree</a></li> <li><a href="/wiki/2%E2%80%933%E2%80%934_tree" title="2–3–4 tree">2–3–4 tree</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=32" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text">For FAT, what is called a "disk block" here is what the FAT documentation calls a "cluster", which is a fixed-size group of one or more contiguous whole physical disk <a href="/wiki/Cylinder-head-sector" title="Cylinder-head-sector">sectors</a>. For the purposes of this discussion, a cluster has no significant difference from a physical sector.</span> </li> <li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text">Two of these were reserved for special purposes, so only 4078 could actually represent disk blocks (clusters).</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=33" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239543626"><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-bayer-mccreight-1970-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-bayer-mccreight-1970_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-bayer-mccreight-1970_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFBayerMcCreight1970" class="citation conference cs1">Bayer, R.; McCreight, E. (July 1970). <a rel="nofollow" class="external text" href="https://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf">"Organization and maintenance of large ordered indices"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '70</i>. Boeing Scientific Research Laboratories. p. 107. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1734663.1734671">10.1145/1734663.1734671</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:26930249">26930249</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Organization+and+maintenance+of+large+ordered+indices&rft.btitle=Proceedings+of+the+1970+ACM+SIGFIDET+%28Now+SIGMOD%29+Workshop+on+Data+Description%2C+Access+and+Control+-+SIGFIDET+%2770&rft.pages=107&rft.pub=Boeing+Scientific+Research+Laboratories&rft.date=1970-07&rft_id=info%3Adoi%2F10.1145%2F1734663.1734671&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A26930249%23id-name%3DS2CID&rft.aulast=Bayer&rft.aufirst=R.&rft.au=McCreight%2C+E.&rft_id=https%3A%2F%2Finfolab.usc.edu%2Fcsci585%2FSpring2010%2Fden_ar%2Findexing.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-FOOTNOTEComer1979-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-FOOTNOTEComer1979_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FOOTNOTEComer1979_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-FOOTNOTEComer1979_2-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-FOOTNOTEComer1979_2-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFComer1979">Comer 1979</a>.</span> </li> <li id="cite_note-FOOTNOTEBayerMcCreight1972-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-FOOTNOTEBayerMcCreight1972_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FOOTNOTEBayerMcCreight1972_3-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-FOOTNOTEBayerMcCreight1972_3-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFBayerMcCreight1972">Bayer & McCreight 1972</a>.</span> </li> <li id="cite_note-FOOTNOTEComer1979123_footnote_1-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEComer1979123_footnote_1_4-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFComer1979">Comer 1979</a>, p. 123 footnote 1.</span> </li> <li id="cite_note-herrenalb-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-herrenalb_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-herrenalb_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWeiner2013" class="citation web cs1">Weiner, Peter G. (30 August 2013). <a rel="nofollow" class="external text" href="https://vimeo.com/73481096">"4- Edward M McCreight"</a> – via Vimeo.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=4-+Edward+M+McCreight&rft.date=2013-08-30&rft.aulast=Weiner&rft.aufirst=Peter+G.&rft_id=https%3A%2F%2Fvimeo.com%2F73481096&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20140604193847/http://scpd.stanford.edu/knuth/index.jsp">"Stanford Center for Professional Development"</a>. <i>scpd.stanford.edu</i>. Archived from <a rel="nofollow" class="external text" href="http://scpd.stanford.edu/knuth/index.jsp">the original</a> on 2014-06-04<span class="reference-accessdate">. Retrieved <span class="nowrap">2011-01-16</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=scpd.stanford.edu&rft.atitle=Stanford+Center+for+Professional+Development&rft_id=http%3A%2F%2Fscpd.stanford.edu%2Fknuth%2Findex.jsp&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-FOOTNOTEKnuth1998483-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-FOOTNOTEKnuth1998483_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FOOTNOTEKnuth1998483_7-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFKnuth1998">Knuth 1998</a>, p. 483.</span> </li> <li id="cite_note-FOOTNOTEFolkZoellick1992362-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEFolkZoellick1992362_8-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFFolkZoellick1992">Folk & Zoellick 1992</a>, p. 362.</span> </li> <li id="cite_note-FOOTNOTEFolkZoellick1992363-9"><span class="mw-cite-backlink">^ <a href="#cite_ref-FOOTNOTEFolkZoellick1992363_9-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FOOTNOTEFolkZoellick1992363_9-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFFolkZoellick1992">Folk & Zoellick 1992</a>, p. 363.</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><a href="#CITEREFBayerMcCreight1972">Bayer & McCreight (1972)</a> avoided the issue by saying an index element is a (physically adjacent) pair of (<i>x</i>, <i>a</i>) where <i>x</i> is the key, and <i>a</i> is some associated information. The associated information might be a pointer to a record or records in a random access, but what it was didn't really matter. <a href="#CITEREFBayerMcCreight1972">Bayer & McCreight (1972)</a> states, "For this paper the associated information is of no further interest."</span> </li> <li id="cite_note-FOOTNOTEFolkZoellick1992379-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEFolkZoellick1992379_11-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFFolkZoellick1992">Folk & Zoellick 1992</a>, p. 379.</span> </li> <li id="cite_note-Navathe2-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-Navathe2_12-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFNavathe2010" class="citation book cs1">Navathe, Ramez Elmasri, Shamkant B. (2010). <i>Fundamentals of database systems</i> (6th ed.). Upper Saddle River, N.J.: Pearson Education. pp. 652–660. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780136086208" title="Special:BookSources/9780136086208"><bdi>9780136086208</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Fundamentals+of+database+systems&rft.place=Upper+Saddle+River%2C+N.J.&rft.pages=652-660&rft.edition=6th&rft.pub=Pearson+Education&rft.date=2010&rft.isbn=9780136086208&rft.aulast=Navathe&rft.aufirst=Ramez+Elmasri%2C+Shamkant+B.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_book" title="Template:Cite book">cite book</a>}}</code>: CS1 maint: multiple names: authors list (<a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">link</a>)</span></span> </li> <li id="cite_note-FOOTNOTEKnuth1998488-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEKnuth1998488_13-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFKnuth1998">Knuth 1998</a>, p. 488.</span> </li> <li id="cite_note-Milo-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-Milo_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Milo_14-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Milo_14-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-Milo_14-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-Milo_14-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-Milo_14-5"><sup><i><b>f</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTomašević2008" class="citation book cs1">Tomašević, Milo (2008). <i>Algorithms and Data Structures</i>. Belgrade, Serbia: Akademska misao. pp. 274–275. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-86-7466-328-8" title="Special:BookSources/978-86-7466-328-8"><bdi>978-86-7466-328-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithms+and+Data+Structures&rft.place=Belgrade%2C+Serbia&rft.pages=274-275&rft.pub=Akademska+misao&rft.date=2008&rft.isbn=978-86-7466-328-8&rft.aulast=Toma%C5%A1evi%C4%87&rft.aufirst=Milo&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRigin_A._M.,_Shershakov_S._A.2019" class="citation journal cs1">Rigin A. M., Shershakov S. A. (2019-09-10). <a rel="nofollow" class="external text" href="https://ispranproceedings.elpub.ru/jour/article/view/1188">"SQLite RDBMS Extension for Data Indexing Using B-tree Modifications"</a>. <i>Proceedings of the Institute for System Programming of the RAS</i>. <b>31</b> (3). Institute for System Programming of the RAS (ISP RAS): 203–216. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.15514%2Fispras-2019-31%283%29-16">10.15514/ispras-2019-31(3)-16</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:203144646">203144646</a><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-08-29</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+Institute+for+System+Programming+of+the+RAS&rft.atitle=SQLite+RDBMS+Extension+for+Data+Indexing+Using+B-tree+Modifications&rft.volume=31&rft.issue=3&rft.pages=203-216&rft.date=2019-09-10&rft_id=info%3Adoi%2F10.15514%2Fispras-2019-31%283%29-16&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A203144646%23id-name%3DS2CID&rft.au=Rigin+A.+M.%2C+Shershakov+S.+A.&rft_id=https%3A%2F%2Fispranproceedings.elpub.ru%2Fjour%2Farticle%2Fview%2F1188&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html">Counted B-Trees</a>, retrieved 2010-01-25</span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation book cs1"><a rel="nofollow" class="external text" href="http://www.seagate.com/staticfiles/support/disc/manuals/NL35%20Series%20&%20BC%20ES%20Series/Barracuda%20ES.2%20Series/100468393f.pdf"><i>Product Manual: Barracuda ES.2 Serial ATA, Rev. F., publication 100468393</i></a> <span class="cs1-format">(PDF)</span>. Seagate Technology LLC. 2008. p. 6.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Product+Manual%3A+Barracuda+ES.2+Serial+ATA%2C+Rev.+F.%2C+publication+100468393&rft.pages=6&rft.pub=Seagate+Technology+LLC&rft.date=2008&rft_id=http%3A%2F%2Fwww.seagate.com%2Fstaticfiles%2Fsupport%2Fdisc%2Fmanuals%2FNL35%2520Series%2520%26%2520BC%2520ES%2520Series%2FBarracuda%2520ES.2%2520Series%2F100468393f.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-kleppmann_2017-18"><span class="mw-cite-backlink">^ <a href="#cite_ref-kleppmann_2017_18-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-kleppmann_2017_18-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-kleppmann_2017_18-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKleppmann2017" class="citation book cs1">Kleppmann, Martin (2017). <a rel="nofollow" class="external text" href="https://www.academia.edu/41298363"><i>Designing Data-Intensive Applications</i></a>. <a href="/wiki/Sebastopol,_California" title="Sebastopol, California">Sebastopol, California</a>: <a href="/wiki/O%27Reilly_Media" title="O'Reilly Media">O'Reilly Media</a>. p. 80. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-449-37332-0" title="Special:BookSources/978-1-449-37332-0"><bdi>978-1-449-37332-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Designing+Data-Intensive+Applications&rft.place=Sebastopol%2C+California&rft.pages=80&rft.pub=O%27Reilly+Media&rft.date=2017&rft.isbn=978-1-449-37332-0&rft.aulast=Kleppmann&rft.aufirst=Martin&rft_id=https%3A%2F%2Fwww.academia.edu%2F41298363&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"> Jan Jannink. "Implementing Deletion in B+-Trees". Section <a rel="nofollow" class="external text" href="https://www.alexdelis.eu/M149/B+deletion.pdf">"4 Lazy Deletion"</a>.</span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><a href="#CITEREFComer1979">Comer 1979</a>, p. 127; <a href="#CITEREFCormenLeisersonRivestStein2001">Cormen et al. 2001</a>, pp. 439–440</span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.cs.rhodes.edu/~kirlinp/courses/db/f16/handouts/btrees-deletion.pdf">"Deletion in a B-tree"</a> <span class="cs1-format">(PDF)</span>. <i>cs.rhodes.edu</i>. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/https://www.cs.rhodes.edu/~kirlinp/courses/db/f16/handouts/btrees-deletion.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09<span class="reference-accessdate">. Retrieved <span class="nowrap">24 May</span> 2022</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=cs.rhodes.edu&rft.atitle=Deletion+in+a+B-tree&rft_id=https%3A%2F%2Fwww.cs.rhodes.edu%2F~kirlinp%2Fcourses%2Fdb%2Ff16%2Fhandouts%2Fbtrees-deletion.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.cs.sunysb.edu/~bender/pub/cache-oblivious-btree.ps">"Cache Oblivious B-trees"</a>. State University of New York (SUNY) at Stony Brook<span class="reference-accessdate">. Retrieved <span class="nowrap">2011-01-17</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Cache+Oblivious+B-trees&rft.pub=State+University+of+New+York+%28SUNY%29+at+Stony+Brook&rft_id=http%3A%2F%2Fwww.cs.sunysb.edu%2F~bender%2Fpub%2Fcache-oblivious-btree.ps&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-insidewin2kntfs-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-insidewin2kntfs_25-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMark_Russinovich2006" class="citation web cs1"><a href="/wiki/Mark_Russinovich" title="Mark Russinovich">Mark Russinovich</a> (30 June 2006). <a rel="nofollow" class="external text" href="http://msdn2.microsoft.com/en-us/library/ms995846.aspx">"Inside Win2K NTFS, Part 1"</a>. <a href="/wiki/MSDN" class="mw-redirect" title="MSDN">Microsoft Developer Network</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20080413181940/http://msdn2.microsoft.com/en-us/library/ms995846.aspx">Archived</a> from the original on 13 April 2008<span class="reference-accessdate">. Retrieved <span class="nowrap">2008-04-18</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Inside+Win2K+NTFS%2C+Part+1&rft.pub=Microsoft+Developer+Network&rft.date=2006-06-30&rft.au=Mark+Russinovich&rft_id=http%3A%2F%2Fmsdn2.microsoft.com%2Fen-us%2Flibrary%2Fms995846.aspx&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMatthew_Dillon2008" class="citation web cs1">Matthew Dillon (2008-06-21). <a rel="nofollow" class="external text" href="https://www.dragonflybsd.org/hammer/hammer.pdf">"The HAMMER Filesystem"</a> <span class="cs1-format">(PDF)</span>. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/https://www.dragonflybsd.org/hammer/hammer.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=The+HAMMER+Filesystem&rft.date=2008-06-21&rft.au=Matthew+Dillon&rft_id=https%3A%2F%2Fwww.dragonflybsd.org%2Fhammer%2Fhammer.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-27">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLehmanYao1981" class="citation journal cs1">Lehman, Philip L.; Yao, s. Bing (1981). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F319628.319663">"Efficient locking for concurrent operations on B-trees"</a>. <i>ACM Transactions on Database Systems</i>. <b>6</b> (4): 650–670. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F319628.319663">10.1145/319628.319663</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10756181">10756181</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Transactions+on+Database+Systems&rft.atitle=Efficient+locking+for+concurrent+operations+on+B-trees&rft.volume=6&rft.issue=4&rft.pages=650-670&rft.date=1981&rft_id=info%3Adoi%2F10.1145%2F319628.319663&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A10756181%23id-name%3DS2CID&rft.aulast=Lehman&rft.aufirst=Philip+L.&rft.au=Yao%2C+s.+Bing&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F319628.319663&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-28"><span class="mw-cite-backlink"><b><a href="#cite_ref-28">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWang1991" class="citation web cs1">Wang, Paul (1 February 1991). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110604175423/http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA232287&Location=U2&doc=GetTRDoc.pdf">"An In-Depth Analysis of Concurrent B-tree Algorithms"</a> <span class="cs1-format">(PDF)</span>. <i>dtic.mil</i>. Archived from <a rel="nofollow" class="external text" href="http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA232287&Location=U2&doc=GetTRDoc.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 4 June 2011<span class="reference-accessdate">. Retrieved <span class="nowrap">21 October</span> 2022</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=dtic.mil&rft.atitle=An+In-Depth+Analysis+of+Concurrent+B-tree+Algorithms&rft.date=1991-02-01&rft.aulast=Wang&rft.aufirst=Paul&rft_id=http%3A%2F%2Fwww.dtic.mil%2Fcgi-bin%2FGetTRDoc%3FAD%3DADA232287%26Location%3DU2%26doc%3DGetTRDoc.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-29"><span class="mw-cite-backlink"><b><a href="#cite_ref-29">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/malbrain/Btree-source-code">"Downloads - high-concurrency-btree - High Concurrency B-Tree code in C - GitHub Project Hosting"</a>. <i><a href="/wiki/GitHub" title="GitHub">GitHub</a></i><span class="reference-accessdate">. Retrieved <span class="nowrap">2014-01-27</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=GitHub&rft.atitle=Downloads+-+high-concurrency-btree+-+High+Concurrency+B-Tree+code+in+C+-+GitHub+Project+Hosting&rft_id=https%3A%2F%2Fgithub.com%2Fmalbrain%2FBtree-source-code&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-30"><span class="mw-cite-backlink"><b><a href="#cite_ref-30">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.freepatentsonline.com/5283894.html">"Lockless concurrent B-tree index meta access method for cached nodes"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Lockless+concurrent+B-tree+index+meta+access+method+for+cached+nodes&rft_id=http%3A%2F%2Fwww.freepatentsonline.com%2F5283894.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></span> </li> <li id="cite_note-31"><span class="mw-cite-backlink"><b><a href="#cite_ref-31">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://lwn.net/Articles/845507/">Introducing maple trees (LWN.net)</a></span> </li> <li id="cite_note-32"><span class="mw-cite-backlink"><b><a href="#cite_ref-32">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://docs.kernel.org/next/core-api/maple_tree.html">Maple Tree (The Linux Kernel documentation)</a></span> </li> <li id="cite_note-33"><span class="mw-cite-backlink"><b><a href="#cite_ref-33">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://lwn.net/Articles/905638/">Introducing the Maple Tree (LWN.net / github)</a></span> </li> </ol></div> <p><span class="noviewer" typeof="mw:File"><span><img alt="Public Domain" src="//upload.wikimedia.org/wikipedia/en/thumb/6/62/PD-icon.svg/12px-PD-icon.svg.png" decoding="async" width="12" height="12" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/6/62/PD-icon.svg/18px-PD-icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/6/62/PD-icon.svg/24px-PD-icon.svg.png 2x" data-file-width="196" data-file-height="196" /></span></span> This article incorporates <a href="/wiki/Copyright_status_of_works_by_the_federal_government_of_the_United_States" title="Copyright status of works by the federal government of the United States">public domain material</a> from <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPaul_E._Black" class="citation cs1">Paul E. Black. <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/abtree.html">"(a,b)-tree"</a>. <i><a href="/wiki/Dictionary_of_Algorithms_and_Data_Structures" class="mw-redirect" title="Dictionary of Algorithms and Data Structures">Dictionary of Algorithms and Data Structures</a></i>. <a href="/wiki/NIST" class="mw-redirect" title="NIST">NIST</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Dictionary+of+Algorithms+and+Data+Structures&rft.atitle=%28a%2Cb%29-tree&rft.au=Paul+E.+Black&rft_id=https%3A%2F%2Fxlinux.nist.gov%2Fdads%2FHTML%2Fabtree.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span> </p> <div class="mw-heading mw-heading2"><h2 id="Sources">Sources</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=34" title="Edit section: Sources"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBayerMcCreight1972" class="citation journal cs1"><a href="/wiki/Rudolf_Bayer" title="Rudolf Bayer">Bayer, R.</a>; <a href="/wiki/Edward_M._McCreight" title="Edward M. McCreight">McCreight, E.</a> (1972). <a rel="nofollow" class="external text" href="https://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf">"Organization and Maintenance of Large Ordered Indexes"</a> <span class="cs1-format">(PDF)</span>. <i>Acta Informatica</i>. <b>1</b> (3): 173–189. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fbf00288683">10.1007/bf00288683</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29859053">29859053</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=Organization+and+Maintenance+of+Large+Ordered+Indexes&rft.volume=1&rft.issue=3&rft.pages=173-189&rft.date=1972&rft_id=info%3Adoi%2F10.1007%2Fbf00288683&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A29859053%23id-name%3DS2CID&rft.aulast=Bayer&rft.aufirst=R.&rft.au=McCreight%2C+E.&rft_id=https%3A%2F%2Finfolab.usc.edu%2Fcsci585%2FSpring2010%2Fden_ar%2Findexing.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFComer1979" class="citation journal cs1"><a href="/wiki/Douglas_Comer" title="Douglas Comer">Comer, Douglas</a> (June 1979). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F356770.356776">"The Ubiquitous B-Tree"</a>. <i>Computing Surveys</i>. <b>11</b> (2): 123–137. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F356770.356776">10.1145/356770.356776</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0360-0300">0360-0300</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:101673">101673</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computing+Surveys&rft.atitle=The+Ubiquitous+B-Tree&rft.volume=11&rft.issue=2&rft.pages=123-137&rft.date=1979-06&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A101673%23id-name%3DS2CID&rft.issn=0360-0300&rft_id=info%3Adoi%2F10.1145%2F356770.356776&rft.aulast=Comer&rft.aufirst=Douglas&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F356770.356776&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCormenLeisersonRivestStein2001" class="citation book cs1"><a href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas</a>; <a href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles</a>; <a href="/wiki/Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Rivest, Ronald</a>; <a href="/wiki/Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2001). <i><a href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a></i> (Second ed.). MIT Press and McGraw-Hill. pp. 434–454. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-262-03293-7" title="Special:BookSources/0-262-03293-7"><bdi>0-262-03293-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Algorithms&rft.pages=434-454&rft.edition=Second&rft.pub=MIT+Press+and+McGraw-Hill&rft.date=2001&rft.isbn=0-262-03293-7&rft.aulast=Cormen&rft.aufirst=Thomas&rft.au=Leiserson%2C+Charles&rft.au=Rivest%2C+Ronald&rft.au=Stein%2C+Clifford&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span> Chapter 18: B-Trees.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFolkZoellick1992" class="citation book cs1">Folk, Michael J.; Zoellick, Bill (1992). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/filestructures00folk"><i>File Structures</i></a></span> (2nd ed.). Addison-Wesley. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-201-55713-4" title="Special:BookSources/0-201-55713-4"><bdi>0-201-55713-4</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=File+Structures&rft.edition=2nd&rft.pub=Addison-Wesley&rft.date=1992&rft.isbn=0-201-55713-4&rft.aulast=Folk&rft.aufirst=Michael+J.&rft.au=Zoellick%2C+Bill&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Ffilestructures00folk&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKnuth1998" class="citation book cs1"><a href="/wiki/Donald_Knuth" title="Donald Knuth">Knuth, Donald</a> (1998). <i>Sorting and Searching</i>. <a href="/wiki/The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>. Vol. 3 (Second ed.). Addison-Wesley. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-201-89685-0" title="Special:BookSources/0-201-89685-0"><bdi>0-201-89685-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Sorting+and+Searching&rft.series=The+Art+of+Computer+Programming&rft.edition=Second&rft.pub=Addison-Wesley&rft.date=1998&rft.isbn=0-201-89685-0&rft.aulast=Knuth&rft.aufirst=Donald&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span> Section 6.2.4: Multiway Trees, pp. 481–491. Also, pp. 476–477 of section 6.2.3 (Balanced Trees) discusses 2–3 trees.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Original_papers">Original papers</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=35" title="Edit section: Original papers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBayerMcCreight1970" class="citation cs2 cs1-prop-long-vol"><a href="/wiki/Rudolf_Bayer" title="Rudolf Bayer">Bayer, Rudolf</a>; <a href="/wiki/Edward_M._McCreight" title="Edward M. McCreight">McCreight, E.</a> (July 1970), <i>Organization and Maintenance of Large Ordered Indices</i>, vol. Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Organization+and+Maintenance+of+Large+Ordered+Indices&rft.pub=Boeing+Scientific+Research+Laboratories&rft.date=1970-07&rft.aulast=Bayer&rft.aufirst=Rudolf&rft.au=McCreight%2C+E.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBayer1971" class="citation conference cs1"><a href="/wiki/Rudolf_Bayer" title="Rudolf Bayer">Bayer, Rudolf</a> (1971). "Binary B-Trees for Virtual Memory". <i>Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control</i>. San Diego, California.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Binary+B-Trees+for+Virtual+Memory&rft.btitle=Proceedings+of+1971+ACM-SIGFIDET+Workshop+on+Data+Description%2C+Access+and+Control&rft.place=San+Diego%2C+California&rft.date=1971&rft.aulast=Bayer&rft.aufirst=Rudolf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=B-tree&action=edit&section=36" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</style><div class="side-box side-box-right plainlinks sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png" decoding="async" width="30" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/45px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/59px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></span></span></div> <div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:B-Trees" class="extiw" title="commons:Category:B-Trees">B-Trees</a></span>.</div></div> </div> <ul><li><a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=I22wEC1tTGo">B-tree lecture</a> by David Scot Taylor, SJSU</li> <li><a rel="nofollow" class="external text" href="https://ysangkok.github.io/js-clrs-btree/btree.html">B-Tree visualisation</a> (click "init")</li> <li><a rel="nofollow" class="external text" href="https://www.cs.usfca.edu/~galles/visualization/BTree.html">Animated B-Tree visualization</a></li> <li><a rel="nofollow" class="external text" href="http://www.scholarpedia.org/article/B-tree_and_UB-tree">B-tree and UB-tree on Scholarpedia</a> Curator: Dr Rudolf Bayer</li> <li><a rel="nofollow" class="external text" href="http://www.bluerwhite.org/btree">B-Trees: Balanced Tree Data Structures</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100305211920/http://www.bluerwhite.org/btree/">Archived</a> 2010-03-05 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/btree.html">NIST's Dictionary of Algorithms and Data Structures: B-tree</a></li> <li><a rel="nofollow" class="external text" href="http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html">B-Tree Tutorial</a></li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20110708080729/http://boilerbay.com/infinitydb/TheDesignOfTheInfinityDatabaseEngine.htm">The InfinityDB BTree implementation</a></li> <li><a rel="nofollow" class="external text" href="http://supertech.csail.mit.edu/cacheObliviousBTree.html">Cache Oblivious B(+)-trees</a></li> <li><a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/bstartree.html">Dictionary of Algorithms and Data Structures entry for B*-tree</a></li> <li><a rel="nofollow" class="external text" href="http://opendatastructures.org/versions/edition-0.1g/ods-python/14_2_B_Trees.html">Open Data Structures - Section 14.2 - B-Trees</a>, <a href="/wiki/Pat_Morin" title="Pat Morin">Pat Morin</a></li> <li><a rel="nofollow" class="external text" href="http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html">Counted B-Trees</a></li> <li><a rel="nofollow" class="external text" href="http://sop.codeplex.com">B-Tree .Net, a modern, virtualized RAM & Disk implementation</a></li></ul> <p><b>Bulk loading</b> </p> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFShetty2010" class="citation thesis cs1">Shetty, Soumya B. (2010). <a rel="nofollow" class="external text" href="https://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=2336&context=etd"><i>A user configurable implementation of B-trees</i></a> (Thesis). Iowa State University.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=A+user+configurable+implementation+of+B-trees&rft.inst=Iowa+State+University&rft.date=2010&rft.aulast=Shetty&rft.aufirst=Soumya+B.&rft_id=https%3A%2F%2Flib.dr.iastate.edu%2Fcgi%2Fviewcontent.cgi%3Farticle%3D2336%26context%3Detd&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKaldırım2015" class="citation web cs1">Kaldırım, Semih (28 April 2015). <a rel="nofollow" class="external text" href="http://www.cs.bilkent.edu.tr/~canf/CS281Spring15LectureNotesFeb13/Week13.pdf">"File Organization, ISAM, B+ Tree and Bulk Loading"</a> <span class="cs1-format">(PDF)</span>. Ankara, Turkey: <a href="/wiki/Bilkent_University" title="Bilkent University">Bilkent University</a>. pp. 4–6. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/http://www.cs.bilkent.edu.tr/~canf/CS281Spring15LectureNotesFeb13/Week13.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=File+Organization%2C+ISAM%2C+B%2B+Tree+and+Bulk+Loading&rft.place=Ankara%2C+Turkey&rft.pages=4-6&rft.pub=Bilkent+University&rft.date=2015-04-28&rft.aulast=Kald%C4%B1r%C4%B1m&rft.aufirst=Semih&rft_id=http%3A%2F%2Fwww.cs.bilkent.edu.tr%2F~canf%2FCS281Spring15LectureNotesFeb13%2FWeek13.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://web.cs.ucdavis.edu/~green/courses/ecs165b-s10/Lecture6.pdf">"ECS 165B: Database System Implementation: Lecture 6"</a> <span class="cs1-format">(PDF)</span>. <a href="/wiki/University_of_California,_Davis" title="University of California, Davis">University of California, Davis</a>. 9 April 2010. p. 23. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/http://web.cs.ucdavis.edu/~green/courses/ecs165b-s10/Lecture6.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=ECS+165B%3A+Database+System+Implementation%3A+Lecture+6&rft.pages=23&rft.pub=University+of+California%2C+Davis&rft.date=2010-04-09&rft_id=http%3A%2F%2Fweb.cs.ucdavis.edu%2F~green%2Fcourses%2Fecs165b-s10%2FLecture6.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.microsoft.com/en-us/sql/t-sql/statements/bulk-insert-transact-sql?view=sql-server-2017">"BULK INSERT (Transact-SQL) in SQL Server 2017"</a>. Microsoft Docs. 6 September 2018.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=BULK+INSERT+%28Transact-SQL%29+in+SQL+Server+2017&rft.pub=Microsoft+Docs&rft.date=2018-09-06&rft_id=https%3A%2F%2Fdocs.microsoft.com%2Fen-us%2Fsql%2Ft-sql%2Fstatements%2Fbulk-insert-transact-sql%3Fview%3Dsql-server-2017&rfr_id=info%3Asid%2Fen.wikipedia.org%3AB-tree" class="Z3988"></span></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Tree_data_structures" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:CS_trees" title="Template:CS trees"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:CS_trees" title="Template talk:CS trees"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:CS_trees" title="Special:EditPage/Template:CS trees"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Tree_data_structures" style="font-size:114%;margin:0 4em"><a href="/wiki/Tree_(abstract_data_type)" title="Tree (abstract data type)">Tree data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Search_tree" title="Search tree">Search trees</a><br />(<a href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">dynamic sets</a>/<a href="/wiki/Associative_array" title="Associative array">associative arrays</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/2%E2%80%933_tree" title="2–3 tree">2–3</a></li> <li><a href="/wiki/2%E2%80%933%E2%80%934_tree" title="2–3–4 tree">2–3–4</a></li> <li><a href="/wiki/AA_tree" title="AA tree">AA</a></li> <li><a href="/wiki/(a,b)-tree" class="mw-redirect" title="(a,b)-tree">(a,b)</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL</a></li> <li><a class="mw-selflink selflink">B</a></li> <li><a href="/wiki/B%2B_tree" title="B+ tree">B+</a></li> <li><a href="/wiki/B*-tree" class="mw-redirect" title="B*-tree">B*</a></li> <li><a href="/wiki/Bx-tree" title="Bx-tree">B<sup>x</sup></a></li> <li>(<a href="/wiki/Optimal_binary_search_tree" title="Optimal binary search tree">Optimal</a>) <a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search</a></li> <li><a href="/wiki/Dancing_tree" title="Dancing tree">Dancing</a></li> <li><a href="/wiki/HTree" title="HTree">HTree</a></li> <li><a href="/wiki/Interval_tree" title="Interval tree">Interval</a></li> <li><a href="/wiki/Order_statistic_tree" title="Order statistic tree">Order statistic</a></li> <li><a href="/wiki/Palindrome_tree" title="Palindrome tree">Palindrome</a></li> <li>(<a href="/wiki/Left-leaning_red%E2%80%93black_tree" title="Left-leaning red–black tree">Left-leaning</a>) <a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black</a></li> <li><a href="/wiki/Scapegoat_tree" title="Scapegoat tree">Scapegoat</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay</a></li> <li><a href="/wiki/T-tree" title="T-tree">T</a></li> <li><a href="/wiki/Treap" title="Treap">Treap</a></li> <li><a href="/wiki/UB-tree" title="UB-tree">UB</a></li> <li><a href="/wiki/Weight-balanced_tree" title="Weight-balanced tree">Weight-balanced</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heaps</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial</a></li> <li><a href="/wiki/Brodal_queue" title="Brodal queue">Brodal</a></li> <li><a href="/wiki/D-ary_heap" title="D-ary heap"><i>d</i>-ary</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci</a></li> <li><a href="/wiki/Leftist_tree" title="Leftist tree">Leftist</a></li> <li><a href="/wiki/Pairing_heap" title="Pairing heap">Pairing</a></li> <li><a href="/wiki/Skew_binomial_heap" title="Skew binomial heap">Skew binomial</a></li> <li><a href="/wiki/Skew_heap" title="Skew heap">Skew</a></li> <li><a href="/wiki/Van_Emde_Boas_tree" title="Van Emde Boas tree">van Emde Boas</a></li> <li><a href="/wiki/Weak_heap" title="Weak heap">Weak</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Trie" title="Trie">Tries</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Ctrie" title="Ctrie">Ctrie</a></li> <li><a href="/wiki/C-trie" title="C-trie">C-trie (compressed ADT)</a></li> <li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash</a></li> <li><a href="/wiki/Radix_tree" title="Radix tree">Radix</a></li> <li><a href="/wiki/Suffix_tree" title="Suffix tree">Suffix</a></li> <li><a href="/wiki/Ternary_search_tree" title="Ternary search tree">Ternary search</a></li> <li><a href="/wiki/X-fast_trie" title="X-fast trie">X-fast</a></li> <li><a href="/wiki/Y-fast_trie" title="Y-fast trie">Y-fast</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Spatial_index" class="mw-redirect" title="Spatial index">Spatial</a> data partitioning trees</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Ball_tree" title="Ball tree">Ball</a></li> <li><a href="/wiki/BK-tree" title="BK-tree">BK</a></li> <li><a href="/wiki/BSP_tree" class="mw-redirect" title="BSP tree">BSP</a></li> <li><a href="/wiki/Cartesian_tree" title="Cartesian tree">Cartesian</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R</a></li> <li><a href="/wiki/K-d_tree" title="K-d tree"><i>k</i>-d</a> (<a href="/wiki/Implicit_k-d_tree" title="Implicit k-d tree">implicit <i>k</i>-d</a>)</li> <li><a href="/wiki/M-tree" title="M-tree">M</a></li> <li><a href="/wiki/Metric_tree" title="Metric tree">Metric</a></li> <li><a href="/wiki/MVP_tree" class="mw-redirect" title="MVP tree">MVP</a></li> <li><a href="/wiki/Octree" title="Octree">Octree</a></li> <li><a href="/wiki/PH-tree" title="PH-tree">PH</a></li> <li><a href="/wiki/Priority_R-tree" title="Priority R-tree">Priority R</a></li> <li><a href="/wiki/Quadtree" title="Quadtree">Quad</a></li> <li><a href="/wiki/R-tree" title="R-tree">R</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+</a></li> <li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R*</a></li> <li><a href="/wiki/Segment_tree" title="Segment tree">Segment</a></li> <li><a href="/wiki/Vantage-point_tree" title="Vantage-point tree">VP</a></li> <li><a href="/wiki/X-tree" title="X-tree">X</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other trees</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cover_tree" title="Cover tree">Cover</a></li> <li><a href="/wiki/Exponential_tree" title="Exponential tree">Exponential</a></li> <li><a href="/wiki/Fenwick_tree" title="Fenwick tree">Fenwick</a></li> <li><a href="/wiki/Finger_tree" title="Finger tree">Finger</a></li> <li><a href="/wiki/Fractal_tree_index" title="Fractal tree index">Fractal tree index</a></li> <li><a href="/wiki/Fusion_tree" title="Fusion tree">Fusion</a></li> <li><a href="/wiki/Hash_calendar" title="Hash calendar">Hash calendar</a></li> <li><a href="/wiki/IDistance" title="IDistance">iDistance</a></li> <li><a href="/wiki/K-ary_tree" class="mw-redirect" title="K-ary tree">K-ary</a></li> <li><a href="/wiki/Left-child_right-sibling_binary_tree" title="Left-child right-sibling binary tree">Left-child right-sibling</a></li> <li><a href="/wiki/Link/cut_tree" title="Link/cut tree">Link/cut</a></li> <li><a href="/wiki/Log-structured_merge-tree" title="Log-structured merge-tree">Log-structured merge</a></li> <li><a href="/wiki/Merkle_tree" title="Merkle tree">Merkle</a></li> <li><a href="/wiki/PQ_tree" title="PQ tree">PQ</a></li> <li><a href="/wiki/Range_tree" title="Range tree">Range</a></li> <li><a href="/wiki/SPQR_tree" title="SPQR tree">SPQR</a></li> <li><a href="/wiki/Top_tree" title="Top tree">Top</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Data_structures" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Data_structures" title="Template:Data structures"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Data_structures" title="Template talk:Data structures"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Data_structures" title="Special:EditPage/Template:Data structures"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_structures" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li> <li><a href="/wiki/Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Associative_array" title="Associative array">Associative array</a> <ul><li><a href="/wiki/Multimap" title="Multimap">Multimap</a></li> <li><a href="/wiki/Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li> <li><a href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">List</a></li> <li><a href="/wiki/Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li> <li><a href="/wiki/Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a> <ul><li><a href="/wiki/Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li> <li><a href="/wiki/Priority_queue" title="Priority queue">Priority queue</a> <ul><li><a href="/wiki/Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li> <li><a href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">Set</a> <ul><li><a href="/wiki/Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li> <li><a href="/wiki/Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_array" title="Bit array">Bit array</a></li> <li><a href="/wiki/Circular_buffer" title="Circular buffer">Circular buffer</a></li> <li><a href="/wiki/Dynamic_array" title="Dynamic array">Dynamic array</a></li> <li><a href="/wiki/Hash_table" title="Hash table">Hash table</a></li> <li><a href="/wiki/Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li> <li><a href="/wiki/Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Association_list" title="Association list">Association list</a></li> <li><a href="/wiki/Linked_list" title="Linked list">Linked list</a></li> <li><a href="/wiki/Skip_list" title="Skip list">Skip list</a></li> <li><a href="/wiki/Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li> <li><a href="/wiki/XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a class="mw-selflink selflink">B-tree</a></li> <li><a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search tree</a> <ul><li><a href="/wiki/AA_tree" title="AA tree">AA tree</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL tree</a></li> <li><a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li> <li><a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay tree</a></li></ul></li> <li><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heap</a> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary heap</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial heap</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a> <ul><li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R* tree</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+ tree</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li> <li><a href="/wiki/Trie" title="Trie">Trie</a> <ul><li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash tree</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li> <li><a href="/wiki/Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li> <li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><a href="/wiki/List_of_data_structures" title="List of data structures">List of data structures</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=B-tree&oldid=1259002079">https://en.wikipedia.org/w/index.php?title=B-tree&oldid=1259002079</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:B-tree" title="Category:B-tree">B-tree</a></li><li><a href="/wiki/Category:Computer-related_introductions_in_1971" title="Category:Computer-related introductions in 1971">Computer-related introductions in 1971</a></li><li><a href="/wiki/Category:Database_index_techniques" title="Category:Database index techniques">Database index techniques</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">CS1 maint: multiple names: authors list</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Wikipedia_articles_with_style_issues_from_May_2022" title="Category:Wikipedia articles with style issues from May 2022">Wikipedia articles with style issues from May 2022</a></li><li><a href="/wiki/Category:All_articles_with_style_issues" title="Category:All articles with style issues">All articles with style issues</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_clarification_from_February_2012" title="Category:Wikipedia articles needing clarification from February 2012">Wikipedia articles needing clarification from February 2012</a></li><li><a href="/wiki/Category:All_Wikipedia_articles_needing_clarification" title="Category:All Wikipedia articles needing clarification">All Wikipedia articles needing clarification</a></li><li><a href="/wiki/Category:All_articles_with_specifically_marked_weasel-worded_phrases" title="Category:All articles with specifically marked weasel-worded phrases">All articles with specifically marked weasel-worded phrases</a></li><li><a href="/wiki/Category:Articles_with_specifically_marked_weasel-worded_phrases_from_September_2019" title="Category:Articles with specifically marked weasel-worded phrases from September 2019">Articles with specifically marked weasel-worded phrases from September 2019</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_April_2018" title="Category:Articles needing additional references from April 2018">Articles needing additional references from April 2018</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_October_2009" title="Category:Articles with unsourced statements from October 2009">Articles with unsourced statements from October 2009</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_May_2020" title="Category:Articles needing additional references from May 2020">Articles needing additional references from May 2020</a></li><li><a href="/wiki/Category:CS1:_long_volume_value" title="Category:CS1: long volume value">CS1: long volume value</a></li><li><a href="/wiki/Category:Commons_category_link_is_on_Wikidata" title="Category:Commons category link is on Wikidata">Commons category link is on Wikidata</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 22 November 2024, at 21:11<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=B-tree&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-5wzkx","wgBackendResponseTime":161,"wgPageParseReport":{"limitreport":{"cputime":"0.843","walltime":"1.142","ppvisitednodes":{"value":6242,"limit":1000000},"postexpandincludesize":{"value":123462,"limit":2097152},"templateargumentsize":{"value":5701,"limit":2097152},"expansiondepth":{"value":17,"limit":100},"expensivefunctioncount":{"value":10,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":127026,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 846.628 1 -total"," 24.19% 204.827 2 Template:Reflist"," 11.25% 95.281 2 Template:Cite_conference"," 9.39% 79.468 1 Template:CS-Trees"," 9.36% 79.204 2 Template:Navbox"," 8.42% 71.264 1 Template:Short_description"," 8.34% 70.593 15 Template:Sfn"," 8.11% 68.675 1 Template:Commons_category"," 6.87% 58.188 1 Template:Sister_project"," 6.63% 56.139 1 Template:Side_box"]},"scribunto":{"limitreport-timeusage":{"value":"0.471","limit":"10.000"},"limitreport-memusage":{"value":8958164,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFBayer1971\"] = 1,\n [\"CITEREFBayerMcCreight1970\"] = 2,\n [\"CITEREFBayerMcCreight1972\"] = 1,\n [\"CITEREFComer1979\"] = 1,\n [\"CITEREFCormenLeisersonRivestStein2001\"] = 1,\n [\"CITEREFFolkZoellick1992\"] = 1,\n [\"CITEREFKaldırım2015\"] = 1,\n [\"CITEREFKleppmann2017\"] = 1,\n [\"CITEREFKnuth1998\"] = 1,\n [\"CITEREFLehmanYao1981\"] = 1,\n [\"CITEREFMark_Russinovich2006\"] = 1,\n [\"CITEREFMatthew_Dillon2008\"] = 1,\n [\"CITEREFNavathe2010\"] = 1,\n [\"CITEREFRigin_A._M.,_Shershakov_S._A.2019\"] = 1,\n [\"CITEREFShetty2010\"] = 1,\n [\"CITEREFTomašević2008\"] = 1,\n [\"CITEREFWang1991\"] = 1,\n [\"CITEREFWeiner2013\"] = 1,\n}\ntemplate_list = table#1 {\n [\"CS-Trees\"] = 1,\n [\"Citation\"] = 1,\n [\"Citation needed\"] = 1,\n [\"Cite book\"] = 7,\n [\"Cite conference\"] = 2,\n [\"Cite journal\"] = 4,\n [\"Cite thesis\"] = 1,\n [\"Cite web\"] = 12,\n [\"Commons category\"] = 1,\n [\"Confusing\"] = 1,\n [\"DADS\"] = 1,\n [\"DEFAULTSORT:B-Tree\"] = 1,\n [\"Data structures\"] = 1,\n [\"Distinguish\"] = 1,\n [\"Floor\"] = 1,\n [\"Harv\"] = 2,\n [\"Harvnb\"] = 2,\n [\"Harvtxt\"] = 2,\n [\"Infobox data structure\"] = 1,\n [\"Math\"] = 10,\n [\"Mvar\"] = 10,\n [\"Nowrap\"] = 4,\n [\"R\"] = 5,\n [\"Reflist\"] = 2,\n [\"Section link\"] = 2,\n [\"Sfn\"] = 15,\n [\"Short description\"] = 1,\n [\"Tone\"] = 1,\n [\"Unreferenced section\"] = 2,\n [\"Webarchive\"] = 1,\n [\"Which\"] = 1,\n}\narticle_whitelist = table#1 {\n}\n"},"cachereport":{"origin":"mw-api-int.codfw.main-849f99967d-4ffjc","timestamp":"20241124053037","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"B-tree","url":"https:\/\/en.wikipedia.org\/wiki\/B-tree","sameAs":"http:\/\/www.wikidata.org\/entity\/Q677051","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q677051","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-11-27T08:55:06Z","dateModified":"2024-11-22T21:11:15Z","headline":"a self-balancing, tree-based data structure, that allows read\/write access in logarithmic time"}</script> </body> </html>