CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>R-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-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-sticky-header-enabled 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":"e3aa253e-63d9-4000-a0fb-44ee79003e52","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"R-tree","wgTitle":"R-tree","wgCurRevisionId":1192723243,"wgRevisionId":1192723243,"wgArticleId":865249,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 maint: multiple names: authors list","Articles with short description","Short description is different from Wikidata","Articles needing additional references from May 2023","All articles needing additional references","All articles with unsourced statements","Articles with unsourced statements from October 2023","Articles to be expanded from October 2011","All articles to be expanded","Articles to be expanded from June 2008","Commons category link is on Wikidata","R-tree"],"wgPageViewLanguage": "en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"R-tree","wgRelevantArticleId":865249,"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":20000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1198051","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","mediawiki.page.gallery.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","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"];</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%7Cmediawiki.page.gallery.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.16"> <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 property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/R-tree.svg/1200px-R-tree.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1028"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/R-tree.svg/800px-R-tree.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="685"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/R-tree.svg/640px-R-tree.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="548"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="R-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/R-tree"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=R-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/R-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-R-tree rootpage-R-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" title="Main menu" > <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><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=R-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=R-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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=R-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=R-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-R-tree_idea" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#R-tree_idea"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>R-tree idea</span> </div> </a> <ul id="toc-R-tree_idea-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Variants" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Variants"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Variants</span> </div> </a> <ul id="toc-Variants-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Algorithm" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Algorithm"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Algorithm</span> </div> </a> <button aria-controls="toc-Algorithm-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 Algorithm subsection</span> </button> <ul id="toc-Algorithm-sublist" class="vector-toc-list"> <li id="toc-Data_layout" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Data_layout"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Data layout</span> </div> </a> <ul id="toc-Data_layout-sublist" class="vector-toc-list"> </ul> </li> <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">3.2</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">3.3</span> <span>Insertion</span> </div> </a> <ul id="toc-Insertion-sublist" class="vector-toc-list"> <li id="toc-Choosing_the_insertion_subtree" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Choosing_the_insertion_subtree"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3.1</span> <span>Choosing the insertion subtree</span> </div> </a> <ul id="toc-Choosing_the_insertion_subtree-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Splitting_an_overflowing_node" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Splitting_an_overflowing_node"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3.2</span> <span>Splitting an overflowing node</span> </div> </a> <ul id="toc-Splitting_an_overflowing_node-sublist" class="vector-toc-list"> </ul> </li> </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">3.4</span> <span>Deletion</span> </div> </a> <ul id="toc-Deletion-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bulk-loading" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bulk-loading"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.5</span> <span>Bulk-loading</span> </div> </a> <ul id="toc-Bulk-loading-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</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" title="Table of Contents" > <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">R-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 16 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-16" 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">16 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/R-strom" title="R-strom – Czech" lang="cs" hreflang="cs" data-title="R-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 mw-list-item"><a href="https://de.wikipedia.org/wiki/R-Baum" title="R-Baum – German" lang="de" hreflang="de" data-title="R-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-R" title="Árbol-R – Spanish" lang="es" hreflang="es" data-title="Árbol-R" 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_%D9%85%D8%B3%D8%AA%D8%B7%DB%8C%D9%84%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/R-arbre" title="R-arbre – French" lang="fr" hreflang="fr" data-title="R-arbre" 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/R_%ED%8A%B8%EB%A6%AC" title="R 트리 – Korean" lang="ko" hreflang="ko" data-title="R 트리" 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/R-stablo" title="R-stablo – Croatian" lang="hr" hreflang="hr" data-title="R-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/R-tree" title="R-tree – Italian" lang="it" hreflang="it" data-title="R-tree" 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_R" title="עץ R – Hebrew" lang="he" hreflang="he" data-title="עץ R" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/R%E6%9C%A8" title="R木 – Japanese" lang="ja" hreflang="ja" data-title="R木" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/R-drzewo" title="R-drzewo – Polish" lang="pl" hreflang="pl" data-title="R-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%81rvores_R" title="Árvores R – Portuguese" lang="pt" hreflang="pt" data-title="Árvores R" 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/R-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="R-дерево (структура данных) – Russian" lang="ru" hreflang="ru" data-title="R-дерево (структура данных)" data-language-autonym="Русский" data-language-local-name="Russian" 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%A0-%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-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/R-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="R-дерево – Ukrainian" lang="uk" hreflang="uk" data-title="R-дерево" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/R%E6%A0%91" title="R树 – Chinese" lang="zh" hreflang="zh" data-title="R树" 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/Q1198051#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/R-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:R-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/R-tree"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=R-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=R-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/R-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=R-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=R-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/R-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/R-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="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=R-tree&oldid=1192723243" 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=R-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=R-tree&id=1192723243&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%2FR-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%2FR-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=R-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=R-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:R-tree" 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/Q1198051" 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">Data structures used in spatial indexing</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">This article is about the data structure. For the type of metric space, see <a href="/wiki/Real_tree" title="Real tree">Real tree</a>.</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-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" 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 article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/R-tree" title="Special:EditPage/R-tree">improve this article</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 removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22R-tree%22">"R-tree"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22R-tree%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22R-tree%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22R-tree%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22R-tree%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22R-tree%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">May 2023</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> <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">R-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">tree</td></tr><tr><th scope="row" class="infobox-label">Invented</th><td class="infobox-data">1984</td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data"><a href="/w/index.php?title=Antonin_Guttman&action=edit&redlink=1" class="new" title="Antonin Guttman (page does not exist)">Antonin Guttman</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(<i>log<sub>M</sub>n</i>)</td><td class="infobox-data infobox-data-b"> O(<i>n</i>)<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Insert</th><td class="infobox-data infobox-data-a"> </td><td class="infobox-data infobox-data-b"> O(<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></tbody></table></td></tr></tbody></table> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:R-tree.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/6f/R-tree.svg/400px-R-tree.svg.png" decoding="async" width="400" height="343" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/6f/R-tree.svg/600px-R-tree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/6f/R-tree.svg/800px-R-tree.svg.png 2x" data-file-width="943" data-file-height="808" /></a><figcaption>Simple example of an R-tree for 2D rectangles</figcaption></figure> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:RTree-Visualization-3D.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/57/RTree-Visualization-3D.svg/400px-RTree-Visualization-3D.svg.png" decoding="async" width="400" height="400" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/57/RTree-Visualization-3D.svg/600px-RTree-Visualization-3D.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/57/RTree-Visualization-3D.svg/800px-RTree-Visualization-3D.svg.png 2x" data-file-width="709" data-file-height="709" /></a><figcaption>Visualization of an R*-tree for 3D points using <a href="/wiki/ELKI" title="ELKI">ELKI</a> (the cubes are directory pages)</figcaption></figure> <p><b>R-trees</b> are <a href="/wiki/Tree_data_structure" class="mw-redirect" title="Tree data structure">tree data structures</a> used for <a href="/wiki/Spatial_index" class="mw-redirect" title="Spatial index">spatial access methods</a>, i.e., for indexing multi-dimensional information such as <a href="/wiki/Geographic_coordinate_system" title="Geographic coordinate system">geographical coordinates</a>, <a href="/wiki/Rectangle" title="Rectangle">rectangles</a> or <a href="/wiki/Polygon" title="Polygon">polygons</a>. The R-tree was proposed by Antonin Guttman in 1984<sup id="cite_ref-guttman_2-0" class="reference"><a href="#cite_note-guttman-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> and has found significant use in both theoretical and applied contexts.<sup id="cite_ref-rtree-book_3-0" class="reference"><a href="#cite_note-rtree-book-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> A common real-world usage for an R-tree might be to store spatial objects such as restaurant locations or the polygons that typical maps are made of: streets, buildings, outlines of lakes, coastlines, etc. and then find answers quickly to queries such as "Find all museums within 2 km of my current location", "retrieve all road segments within 2 km of my location" (to display them in a <a href="/wiki/Navigation_system" title="Navigation system">navigation system</a>) or "find the nearest gas station" (although not taking roads into account). The R-tree can also accelerate <a href="/wiki/Nearest_neighbor_search" title="Nearest neighbor search">nearest neighbor search</a><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> for various distance metrics, including <a href="/wiki/Great-circle_distance" title="Great-circle distance">great-circle distance</a>.<sup id="cite_ref-geodetic_5-0" class="reference"><a href="#cite_note-geodetic-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="R-tree_idea">R-tree idea</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=R-tree&action=edit&section=1" title="Edit section: R-tree idea"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The key idea of the data structure is to group nearby objects and represent them with their <a href="/wiki/Minimum_bounding_rectangle" title="Minimum bounding rectangle">minimum bounding rectangle</a> in the next higher level of the tree; the "R" in R-tree is for rectangle. Since all objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects. At the leaf level, each rectangle describes a single object; at higher levels the aggregation includes an increasing number of objects. This can also be seen as an increasingly coarse approximation of the data set. </p><p>Similar to the <a href="/wiki/B-tree" title="B-tree">B-tree</a>, the R-tree is also a balanced search tree (so all leaf nodes are at the same depth), organizes the data in pages, and is designed for storage on disk (as used in <a href="/wiki/Database" title="Database">databases</a>). Each page can contain a maximum number of entries, often denoted as <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 M}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>M</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}"></span>. It also guarantees a minimum fill (except for the root node), however best performance has been experienced with a minimum fill of 30%–40% of the maximum number of entries (B-trees guarantee 50% page fill, and <a href="/wiki/B*-tree" class="mw-redirect" title="B*-tree">B*-trees</a> even 66%). The reason for this is the more complex balancing required for spatial data as opposed to linear data stored in B-trees. </p><p>As with most trees, the searching algorithms (e.g., <a href="/wiki/Intersection_(set_theory)" title="Intersection (set theory)">intersection</a>, containment, <a href="/wiki/Nearest_neighbor_search" title="Nearest neighbor search">nearest neighbor search</a>) are rather simple. The key idea is to use the bounding boxes to decide whether or not to search inside a subtree. In this way, most of the nodes in the tree are never read during a search. Like B-trees, R-trees are suitable for large data sets and <a href="/wiki/Database" title="Database">databases</a>, where nodes can be paged to memory when needed, and the whole tree cannot be kept in main memory. Even if data can be fit in memory (or cached), the R-trees in most practical applications will usually provide performance advantages over naive check of all objects when the number of objects is more than few hundred or so. However, for in-memory applications, there are similar alternatives that can provide slightly better performance or be simpler to implement in practice. <sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="Not only would it be nice to provide proof, but also, for readers interested in this area, it would be useful to see the more memory-suited methods (October 2023)">citation needed</span></a></i>]</sup> To maintain in-memory computing for R-tree in a computer cluster where computing nodes are connected by a network, researchers have used RDMA (<a href="/wiki/Remote_direct_memory_access" title="Remote direct memory access">Remote Direct Memory Access</a>) to implement data-intensive applications under R-tree in a distributed environment.<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> This approach is scalable for increasingly large applications and achieves high throughput and low latency performance for R-tree. </p><p>The key difficulty of R-tree is to build an efficient tree that on one hand is balanced (so the leaf nodes are at the same height) on the other hand the rectangles do not cover too much empty space and do not overlap too much (so that during search, fewer subtrees need to be processed). For example, the original idea for inserting elements to obtain an efficient tree is to always insert into the subtree that requires least enlargement of its bounding box. Once that page is full, the data is split into two sets that should cover the minimal area each. Most of the research and improvements for R-trees aims at improving the way the tree is built and can be grouped into two objectives: building an efficient tree from scratch (known as bulk-loading) and performing changes on an existing tree (insertion and deletion). </p><p>R-trees do not guarantee good <a href="/wiki/Worst-case_performance" class="mw-redirect" title="Worst-case performance">worst-case performance</a>, but generally perform well with real-world data.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> While more of theoretical interest, the (bulk-loaded) <a href="/wiki/Priority_R-tree" title="Priority R-tree">Priority R-tree</a> variant of the R-tree is worst-case optimal,<sup id="cite_ref-prtree_8-0" class="reference"><a href="#cite_note-prtree-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> but due to the increased complexity, has not received much attention in practical applications so far. </p><p>When data is organized in an R-tree, the neighbors within a given distance r and the <a href="/wiki/K_nearest_neighbors" class="mw-redirect" title="K nearest neighbors">k nearest neighbors</a> (for any <a href="/wiki/Lp_space" title="Lp space">L<sup>p</sup>-Norm</a>) of all points can efficiently be computed using a spatial join.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><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> This is beneficial for many algorithms based on such queries, for example the <a href="/wiki/Local_Outlier_Factor" class="mw-redirect" title="Local Outlier Factor">Local Outlier Factor</a>. DeLi-Clu,<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> Density-Link-Clustering is a <a href="/wiki/Cluster_analysis" title="Cluster analysis">cluster analysis</a> algorithm that uses the R-tree structure for a similar kind of spatial join to efficiently compute an <a href="/wiki/OPTICS_algorithm" title="OPTICS algorithm">OPTICS</a> clustering. </p> <div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=R-tree&action=edit&section=2" title="Edit section: Variants"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Priority_R-tree" title="Priority R-tree">Priority R-tree</a></li> <li><a href="/wiki/R*-tree" 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> <li><a href="/wiki/X-tree" title="X-tree">X-tree</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=R-tree&action=edit&section=3" title="Edit section: Algorithm"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Data_layout">Data layout</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=R-tree&action=edit&section=4" title="Edit section: Data layout"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Data in R-trees is organized in pages that can have a variable number of entries (up to some pre-defined maximum, and usually above a minimum fill). Each entry within a non-<a href="/wiki/Leaf_node" class="mw-redirect" title="Leaf node">leaf node</a> stores two pieces of data: a way of identifying a <a href="/wiki/Child_node" class="mw-redirect" title="Child node">child node</a>, and the <a href="/wiki/Bounding_box" class="mw-redirect" title="Bounding box">bounding box</a> of all entries within this child node. Leaf nodes store the data required for each child, often a point or bounding box representing the child and an external identifier for the child. For point data, the leaf entries can be just the points themselves. For polygon data (that often requires the storage of large polygons) the common setup is to store only the MBR (minimum bounding rectangle) of the polygon along with a unique identifier in the tree. </p> <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=R-tree&action=edit&section=5" title="Edit section: Search"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In <a href="/wiki/Range_searching" title="Range searching">range searching</a>, the input is a search rectangle (Query box). Searching is quite similar to searching in a <a href="/wiki/B%2B_tree" title="B+ tree">B+ tree</a>. The search starts from the root node of the tree. Every internal node contains a set of rectangles and pointers to the corresponding child node and every leaf node contains the rectangles of spatial objects (the pointer to some spatial object can be there). For every rectangle in a node, it has to be decided if it overlaps the search rectangle or not. If yes, the corresponding child node has to be searched also. Searching is done like this in a recursive manner until all overlapping nodes have been traversed. When a leaf node is reached, the contained bounding boxes (rectangles) are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle. </p><p>For priority search such as <a href="/wiki/Nearest_neighbor_search" title="Nearest neighbor search">nearest neighbor search</a>, the query consists of a point or rectangle. The root node is inserted into the priority queue. Until the queue is empty or the desired number of results have been returned the search continues by processing the nearest entry in the queue. Tree nodes are expanded and their children reinserted. Leaf entries are returned when encountered in the queue.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> This approach can be used with various distance metrics, including <a href="/wiki/Great-circle_distance" title="Great-circle distance">great-circle distance</a> for geographic data.<sup id="cite_ref-geodetic_5-1" class="reference"><a href="#cite_note-geodetic-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </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=R-tree&action=edit&section=6" title="Edit section: Insertion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To insert an object, the tree is traversed recursively from the root node. At each step, all rectangles in the current directory node are examined, and a candidate is chosen using a heuristic such as choosing the rectangle which requires least enlargement. The search then descends into this page, until reaching a leaf node. If the leaf node is full, it must be split before the insertion is made. Again, since an exhaustive search is too expensive, a heuristic is employed to split the node into two. Adding the newly created node to the previous level, this level can again overflow, and these overflows can propagate up to the root node; when this node also overflows, a new root node is created and the tree has increased in height. </p> <div class="mw-heading mw-heading4"><h4 id="Choosing_the_insertion_subtree">Choosing the insertion subtree</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=R-tree&action=edit&section=7" title="Edit section: Choosing the insertion subtree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The algorithm needs to decide in which subtree to insert. When a data object is fully contained in a single rectangle, the choice is clear. When there are multiple options or rectangles in need of enlargement, the choice can have a significant impact on the performance of the tree. </p><p>The objects are inserted into the subtree that needs the least enlargement. A Mixture heuristic is employed throughout. What happens next is it tries to minimize the overlap (in case of ties, prefer least enlargement and then least area); at the higher levels, it behaves similar to the R-tree, but on ties again preferring the subtree with smaller area. The decreased overlap of rectangles in the <a href="/wiki/R*-tree" title="R*-tree">R*-tree</a> is one of the key benefits over the traditional R-tree. </p> <div class="mw-heading mw-heading4"><h4 id="Splitting_an_overflowing_node">Splitting an overflowing node</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=R-tree&action=edit&section=8" title="Edit section: Splitting an overflowing node"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Since redistributing all objects of a node into two nodes has an exponential number of options, a heuristic needs to be employed to find the best split. In the classic R-tree, Guttman proposed two such heuristics, called QuadraticSplit and LinearSplit. In quadratic split, the algorithm searches for the pair of rectangles that is the worst combination to have in the same node, and puts them as initial objects into the two new groups. It then searches for the entry which has the strongest preference for one of the groups (in terms of area increase) and assigns the object to this group until all objects are assigned (satisfying the minimum fill). </p><p>There are other splitting strategies such as Greene's Split,<sup id="cite_ref-greene_13-0" class="reference"><a href="#cite_note-greene-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> the <a href="/wiki/R*-tree" title="R*-tree">R*-tree</a> splitting heuristic<sup id="cite_ref-rstar_14-0" class="reference"><a href="#cite_note-rstar-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> (which again tries to minimize overlap, but also prefers quadratic pages) or the linear split algorithm proposed by Ang and Tan<sup id="cite_ref-ang-tan_15-0" class="reference"><a href="#cite_note-ang-tan-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> (which however can produce very irregular rectangles, which are less performant for many real world range and window queries). In addition to having a more advanced splitting heuristic, the <a href="/wiki/R*-tree" title="R*-tree">R*-tree</a> also tries to avoid splitting a node by reinserting some of the node members, which is similar to the way a <a href="/wiki/B-tree" title="B-tree">B-tree</a> balances overflowing nodes. This was shown to also reduce overlap and thus increase tree performance. </p><p>Finally, the <a href="/wiki/X-tree" title="X-tree">X-tree</a><sup id="cite_ref-xtree2_16-0" class="reference"><a href="#cite_note-xtree2-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> can be seen as a R*-tree variant that can also decide to not split a node, but construct a so-called super-node containing all the extra entries, when it doesn't find a good split (in particular for high-dimensional data). </p> <style data-mw-deduplicate="TemplateStyles:r1275594942">@media all and (max-width:720px){.mw-parser-output .mod-gallery{width:100%!important}}.mw-parser-output .mod-gallery{display:table}.mw-parser-output .mod-gallery-default{background:transparent;margin-top:4px}.mw-parser-output .mod-gallery-center{margin-left:auto;margin-right:auto}.mw-parser-output .mod-gallery-left{float:left}.mw-parser-output .mod-gallery-right{float:right}.mw-parser-output .mod-gallery-none{float:none}.mw-parser-output .mod-gallery-center .gallery{justify-content:center}.mw-parser-output .mod-gallery-left .gallery{justify-content:left}.mw-parser-output .mod-gallery-right .gallery{justify-content:right}.mw-parser-output .mod-gallery-collapsible{width:100%}.mw-parser-output .mod-gallery .title,.mw-parser-output .mod-gallery .main,.mw-parser-output .mod-gallery .footer{display:table-row}.mw-parser-output .mod-gallery .title>div{display:table-cell;padding:0 4px 4px;text-align:center;font-weight:bold}.mw-parser-output .mod-gallery .main>div{display:table-cell}.mw-parser-output .mod-gallery .gallery.gallery.gallery{line-height:1.35em;display:flex;flex-wrap:wrap;column-gap:4px}.mw-parser-output .mod-gallery .footer>div{display:table-cell;padding:4px;text-align:right;font-size:85%;line-height:1em}.mw-parser-output .mod-gallery .title>div *,.mw-parser-output .mod-gallery .footer>div *{overflow:visible}.mw-parser-output .mod-gallery .gallerybox img{background:none!important}.mw-parser-output .mod-gallery .bordered-images .thumb img{outline:solid var(--background-color-neutral,#eaecf0)1px}.mw-parser-output .mod-gallery .whitebg .thumb{background:var(--background-color-base,#fff)!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .mod-gallery .bordered-images .thumb img[alt*="\200b \200b \200b "],html.skin-theme-clientpref-night .mw-parser-output .skin-invert-image .mod-gallery .whitebg .thumb.thumb.thumb img{outline:solid #d7d7d7 1px}html.skin-theme-clientpref-night .mw-parser-output .skin-invert-image .mod-gallery .whitebg .thumb.thumb.thumb img{background:none!important}html.skin-theme-clientpref-night .mw-parser-output .mod-gallery .whitebg .thumb img:not([alt*="\200b \200b \200b "]):not([alt*="\200b \200b \200c "]){background:white!important}html.skin-theme-clientpref-night .mw-parser-output .mod-gallery img[alt*="\200b \200b \200b "]{filter:invert(1)hue-rotate(180deg)}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .mod-gallery .bordered-images .thumb img[alt*="\200b \200b \200b "],html.skin-theme-clientpref-os .mw-parser-output .skin-invert-image .mod-gallery .whitebg .thumb.thumb.thumb img{outline:solid #d7d7d7 1px}html.skin-theme-clientpref-os .mw-parser-output .skin-invert-image .mod-gallery .whitebg .thumb.thumb.thumb img{background:none!important}html.skin-theme-clientpref-os .mw-parser-output .mod-gallery .whitebg .thumb img:not([alt*="\200b \200b \200b "]):not([alt*="\200b \200b \200c "]){background:white!important}html.skin-theme-clientpref-os .mw-parser-output .mod-gallery img[alt*="\200b \200b \200b "]{filter:invert(1)hue-rotate(180deg)}}</style><div class="mod-gallery mod-gallery-default mod-gallery-center"><div class="title"><div>Effect of different splitting heuristics on a database with US postal districts</div></div><div class="main"><div><ul class="gallery mw-gallery-traditional nochecker bordered-images whitebg"> <li class="gallerybox" style="width: 335px"> <div class="thumb" style="width: 330px; height: 330px;"><span typeof="mw:File"><a href="/wiki/File:R-tree_with_Guttman%27s_quadratic_split.png" class="mw-file-description" title="Guttman's quadratic split.[2] Pages in this tree overlap a lot."><img alt="Guttman's quadratic split., Pages in this tree overlap a lot." src="//upload.wikimedia.org/wikipedia/commons/thumb/5/5b/R-tree_with_Guttman%27s_quadratic_split.png/300px-R-tree_with_Guttman%27s_quadratic_split.png" decoding="async" width="300" height="300" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/5b/R-tree_with_Guttman%27s_quadratic_split.png/450px-R-tree_with_Guttman%27s_quadratic_split.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/5b/R-tree_with_Guttman%27s_quadratic_split.png/600px-R-tree_with_Guttman%27s_quadratic_split.png 2x" data-file-width="709" data-file-height="709" /></a></span></div> <div class="gallerytext">Guttman's quadratic split.<sup id="cite_ref-guttman_2-1" class="reference"><a href="#cite_note-guttman-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><br />Pages in this tree overlap a lot.</div> </li> <li class="gallerybox" style="width: 335px"> <div class="thumb" style="width: 330px; height: 330px;"><span typeof="mw:File"><a href="/wiki/File:R-tree_built_with_Guttman%27s_linear_split.png" class="mw-file-description" title="Guttman's linear split.[2] Even worse structure, but also faster to construct."><img alt="Guttman's linear split., Even worse structure, but also faster to construct." src="//upload.wikimedia.org/wikipedia/commons/thumb/0/02/R-tree_built_with_Guttman%27s_linear_split.png/300px-R-tree_built_with_Guttman%27s_linear_split.png" decoding="async" width="300" height="300" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/0/02/R-tree_built_with_Guttman%27s_linear_split.png/450px-R-tree_built_with_Guttman%27s_linear_split.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/0/02/R-tree_built_with_Guttman%27s_linear_split.png/600px-R-tree_built_with_Guttman%27s_linear_split.png 2x" data-file-width="709" data-file-height="709" /></a></span></div> <div class="gallerytext">Guttman's linear split.<sup id="cite_ref-guttman_2-2" class="reference"><a href="#cite_note-guttman-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><br />Even worse structure, but also faster to construct.</div> </li> <li class="gallerybox" style="width: 335px"> <div class="thumb" style="width: 330px; height: 330px;"><span typeof="mw:File"><a href="/wiki/File:R-tree_built_with_Greenes_Split.png" class="mw-file-description" title="Greene's split.[13] Pages overlap much less than with Guttman's strategy."><img alt="Greene's split. Pages overlap much less than with Guttman's strategy." src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1d/R-tree_built_with_Greenes_Split.png/300px-R-tree_built_with_Greenes_Split.png" decoding="async" width="300" height="300" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1d/R-tree_built_with_Greenes_Split.png/450px-R-tree_built_with_Greenes_Split.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1d/R-tree_built_with_Greenes_Split.png/600px-R-tree_built_with_Greenes_Split.png 2x" data-file-width="709" data-file-height="709" /></a></span></div> <div class="gallerytext">Greene's split.<sup id="cite_ref-greene_13-1" class="reference"><a href="#cite_note-greene-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> Pages overlap much less than with Guttman's strategy.</div> </li> <li class="gallerybox" style="width: 335px"> <div class="thumb" style="width: 330px; height: 330px;"><span typeof="mw:File"><a href="/wiki/File:R-tree_built_with_Ang-Tan_linear_split.png" class="mw-file-description" title="Ang-Tan linear split.[15] This strategy produces sliced pages, which often yield bad query performance."><img alt="Ang-Tan linear split., This strategy produces sliced pages, which often yield bad query performance." src="//upload.wikimedia.org/wikipedia/commons/thumb/8/8a/R-tree_built_with_Ang-Tan_linear_split.png/300px-R-tree_built_with_Ang-Tan_linear_split.png" decoding="async" width="300" height="300" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/8a/R-tree_built_with_Ang-Tan_linear_split.png/450px-R-tree_built_with_Ang-Tan_linear_split.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/8a/R-tree_built_with_Ang-Tan_linear_split.png/600px-R-tree_built_with_Ang-Tan_linear_split.png 2x" data-file-width="709" data-file-height="709" /></a></span></div> <div class="gallerytext">Ang-Tan linear split.<sup id="cite_ref-ang-tan_15-1" class="reference"><a href="#cite_note-ang-tan-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><br />This strategy produces sliced pages, which often yield bad query performance.</div> </li> <li class="gallerybox" style="width: 335px"> <div class="thumb" style="width: 330px; height: 330px;"><span typeof="mw:File"><a href="/wiki/File:R*-tree_built_using_topological_split.png" class="mw-file-description" title="R* tree topological split.[14] The pages overlap much less since the R*-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy prefers quadratic pages, which yields better performance for common map applications."><img alt="R* tree topological split., The pages overlap much less since the R*-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy prefers quadratic pages, which yields better performance for common map applications." src="//upload.wikimedia.org/wikipedia/commons/thumb/4/46/R%2A-tree_built_using_topological_split.png/300px-R%2A-tree_built_using_topological_split.png" decoding="async" width="300" height="300" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/46/R%2A-tree_built_using_topological_split.png/450px-R%2A-tree_built_using_topological_split.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/46/R%2A-tree_built_using_topological_split.png/600px-R%2A-tree_built_using_topological_split.png 2x" data-file-width="709" data-file-height="709" /></a></span></div> <div class="gallerytext"><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R* tree</a> topological split.<sup id="cite_ref-rstar_14-1" class="reference"><a href="#cite_note-rstar-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><br /> The pages overlap much less since the R*-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy prefers quadratic pages, which yields better performance for common map applications.</div> </li> <li class="gallerybox" style="width: 335px"> <div class="thumb" style="width: 330px; height: 330px;"><span typeof="mw:File"><a href="/wiki/File:R*-tree_bulk_loaded_with_sort-tile-recursive.png" class="mw-file-description" title="Bulk loaded R* tree using Sort-Tile-Recursive (STR). The leaf pages do not overlap at all, and the directory pages overlap only little. This is a very efficient tree, but it requires the data to be completely known beforehand."><img alt="Bulk loaded R* tree using Sort-Tile-Recursive (STR)., The leaf pages do not overlap at all, and the directory pages overlap only little. This is a very efficient tree, but it requires the data to be completely known beforehand." src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1e/R%2A-tree_bulk_loaded_with_sort-tile-recursive.png/300px-R%2A-tree_bulk_loaded_with_sort-tile-recursive.png" decoding="async" width="300" height="300" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1e/R%2A-tree_bulk_loaded_with_sort-tile-recursive.png/450px-R%2A-tree_bulk_loaded_with_sort-tile-recursive.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1e/R%2A-tree_bulk_loaded_with_sort-tile-recursive.png/600px-R%2A-tree_bulk_loaded_with_sort-tile-recursive.png 2x" data-file-width="709" data-file-height="709" /></a></span></div> <div class="gallerytext">Bulk loaded <a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R* tree</a> using Sort-Tile-Recursive (STR).<br />The leaf pages do not overlap at all, and the directory pages overlap only little. This is a very efficient tree, but it requires the data to be completely known beforehand.</div> </li> <li class="gallerybox" style="width: 335px"> <div class="thumb" style="width: 330px; height: 330px;"><span typeof="mw:File"><a href="/wiki/File:M-tree_built_with_MMRad_split.png" class="mw-file-description" title="M-trees are similar to the R-tree, but use nested spherical pages. Splitting these pages is, however, much more complicated and pages usually overlap much more."><img alt="M-trees are similar to the R-tree, but use nested spherical pages., Splitting these pages is, however, much more complicated and pages usually overlap much more." src="//upload.wikimedia.org/wikipedia/commons/thumb/7/7b/M-tree_built_with_MMRad_split.png/300px-M-tree_built_with_MMRad_split.png" decoding="async" width="300" height="213" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/7b/M-tree_built_with_MMRad_split.png/450px-M-tree_built_with_MMRad_split.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/7b/M-tree_built_with_MMRad_split.png/600px-M-tree_built_with_MMRad_split.png 2x" data-file-width="1000" data-file-height="709" /></a></span></div> <div class="gallerytext"><a href="/wiki/M-tree" title="M-tree">M-trees</a> are similar to the R-tree, but use nested spherical pages.<br />Splitting these pages is, however, much more complicated and pages usually overlap much more.</div> </li> </ul></div></div></div> <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=R-tree&action=edit&section=9" title="Edit section: Deletion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Deleting an entry from a page may require updating the bounding rectangles of parent pages. However, when a page is underfull, it will not be balanced with its neighbors. Instead, the page will be dissolved and all its children (which may be subtrees, not only leaf objects) will be reinserted. If during this process the root node has a single element, the tree height can decrease. </p> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Expand_section plainlinks metadata ambox mbox-small-left ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><span typeof="mw:File"><a href="/wiki/File:Wiki_letter_w_cropped.svg" class="mw-file-description"><img alt="[icon]" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png" decoding="async" width="20" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/30px-Wiki_letter_w_cropped.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/40px-Wiki_letter_w_cropped.svg.png 2x" data-file-width="44" data-file-height="31" /></a></span></td><td class="mbox-text"><div class="mbox-text-span">This section <b>needs expansion</b>. You can help by <a class="external text" href="https://en.wikipedia.org/w/index.php?title=R-tree&action=edit&section=">adding to it</a>. <span class="date-container"><i>(<span class="date">October 2011</span>)</i></span></div></td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Bulk-loading">Bulk-loading</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=R-tree&action=edit&section=10" title="Edit section: Bulk-loading"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Nearest-X: Objects are sorted by their first coordinate ("X") and then split into pages of the desired size.</li> <li>Packed <a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a>: variation of Nearest-X, but sorting using the Hilbert value of the center of a rectangle instead of using the X coordinate. There is no guarantee the pages will not overlap.</li> <li>Sort-Tile-Recursive (STR):<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> Another variation of Nearest-X, that estimates the total number of leaves required as <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 l=\lceil {\text{number of objects}}/{\text{capacity}}\rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>l</mi> <mo>=</mo> <mo fence="false" stretchy="false">⌈</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>number of objects</mtext> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mtext>capacity</mtext> </mrow> <mo fence="false" stretchy="false">⌉</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle l=\lceil {\text{number of objects}}/{\text{capacity}}\rceil }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6c3fbcf62709eba7c05620fbeb51918a0ebe7d57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.326ex; height:2.843ex;" alt="{\displaystyle l=\lceil {\text{number of objects}}/{\text{capacity}}\rceil }"></span>, the required split factor in each dimension to achieve this as <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 s=\lceil l^{1/d}\rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo>=</mo> <mo fence="false" stretchy="false">⌈</mo> <msup> <mi>l</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>d</mi> </mrow> </msup> <mo fence="false" stretchy="false">⌉</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s=\lceil l^{1/d}\rceil }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/51772bdc30a1bd90f72befdafc257ec49fc64937" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.683ex; height:3.343ex;" alt="{\displaystyle s=\lceil l^{1/d}\rceil }"></span>, then repeatedly splits each dimensions successively into <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 s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}"></span> equal sized partitions using 1-dimensional sorting. The resulting pages, if they occupy more than one page, are again bulk-loaded using the same algorithm. For point data, the leaf nodes will not overlap, and "tile" the data space into approximately equal sized pages.</li> <li>Overlap Minimizing Top-down (OMT):<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> Improvement over STR using a top-down approach which minimizes overlaps between slices and improves query performance.</li> <li><a href="/wiki/Priority_R-tree" title="Priority R-tree">Priority R-tree</a></li></ul> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Expand_section plainlinks metadata ambox mbox-small-left ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><span typeof="mw:File"><a href="/wiki/File:Wiki_letter_w_cropped.svg" class="mw-file-description"><img alt="[icon]" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png" decoding="async" width="20" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/30px-Wiki_letter_w_cropped.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/40px-Wiki_letter_w_cropped.svg.png 2x" data-file-width="44" data-file-height="31" /></a></span></td><td class="mbox-text"><div class="mbox-text-span">This section <b>needs expansion</b>. You can help by <a class="external text" href="https://en.wikipedia.org/w/index.php?title=R-tree&action=edit&section=">adding to it</a>. <span class="date-container"><i>(<span class="date">June 2008</span>)</i></span></div></td></tr></tbody></table> <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=R-tree&action=edit&section=11" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Segment_tree" title="Segment tree">Segment tree</a></li> <li><a href="/wiki/Interval_tree" title="Interval tree">Interval tree</a> – A degenerate R-tree for one dimension (usually time).</li> <li><a href="/wiki/K-d_tree" title="K-d tree">K-d tree</a></li> <li><a href="/wiki/Bounding_volume_hierarchy" title="Bounding volume hierarchy">Bounding volume hierarchy</a></li> <li><a href="/wiki/Spatial_index" class="mw-redirect" title="Spatial index">Spatial index</a></li> <li><a href="/wiki/GiST" title="GiST">GiST</a></li></ul> <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=R-tree&action=edit&section=12" title="Edit section: References"><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 mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www2.cs.sfu.ca/CourseCentral/454/jpei/slides/R-Tree.pdf">R Tree</a> cs.sfu.ca</span> </li> <li id="cite_note-guttman-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-guttman_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-guttman_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-guttman_2-2"><sup><i><b>c</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="CITEREFGuttman1984" class="citation book cs1">Guttman, A. (1984). <a rel="nofollow" class="external text" href="http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf">"R-Trees: A Dynamic Index Structure for Spatial Searching"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the 1984 ACM SIGMOD international conference on Management of data – SIGMOD '84</i>. p. 47. <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%2F602259.602266">10.1145/602259.602266</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0897911283" title="Special:BookSources/978-0897911283"><bdi>978-0897911283</bdi></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:876601">876601</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=R-Trees%3A+A+Dynamic+Index+Structure+for+Spatial+Searching&rft.btitle=Proceedings+of+the+1984+ACM+SIGMOD+international+conference+on+Management+of+data+%E2%80%93+SIGMOD+%2784&rft.pages=47&rft.date=1984&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A876601%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F602259.602266&rft.isbn=978-0897911283&rft.aulast=Guttman&rft.aufirst=A.&rft_id=http%3A%2F%2Fwww-db.deis.unibo.it%2Fcourses%2FSI-LS%2Fpapers%2FGut84.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-rtree-book-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-rtree-book_3-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFY._ManolopoulosA._NanopoulosY._Theodoridis2006" class="citation book cs1">Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=1mu099DN9UwC&pg=PR5"><i>R-Trees: Theory and Applications</i></a>. Springer. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-85233-977-7" title="Special:BookSources/978-1-85233-977-7"><bdi>978-1-85233-977-7</bdi></a><span class="reference-accessdate">. Retrieved <span class="nowrap">8 October</span> 2011</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=R-Trees%3A+Theory+and+Applications&rft.pub=Springer&rft.date=2006&rft.isbn=978-1-85233-977-7&rft.au=Y.+Manolopoulos&rft.au=A.+Nanopoulos&rft.au=Y.+Theodoridis&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D1mu099DN9UwC%26pg%3DPR5&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRoussopoulosKelleyVincent1995" class="citation conference cs1">Roussopoulos, N.; Kelley, S.; Vincent, F. D. R. (1995). "Nearest neighbor queries". <i>Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95</i>. p. 71. <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%2F223784.223794">10.1145/223784.223794</a></span>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0897917316" title="Special:BookSources/0897917316"><bdi>0897917316</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Nearest+neighbor+queries&rft.btitle=Proceedings+of+the+1995+ACM+SIGMOD+international+conference+on+Management+of+data+%E2%80%93+SIGMOD+%2795&rft.pages=71&rft.date=1995&rft_id=info%3Adoi%2F10.1145%2F223784.223794&rft.isbn=0897917316&rft.aulast=Roussopoulos&rft.aufirst=N.&rft.au=Kelley%2C+S.&rft.au=Vincent%2C+F.+D.+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-geodetic-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-geodetic_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-geodetic_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="CITEREFSchubertZimekKriegel2013" class="citation conference cs1">Schubert, E.; Zimek, A.; <a href="/wiki/Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Kriegel, H. P.</a> (2013). "Geodetic Distance Queries on R-Trees for Indexing Geographic Data". <i>Advances in Spatial and Temporal Databases</i>. Lecture Notes in Computer Science. Vol. 8098. p. 146. <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%2F978-3-642-40235-7_9">10.1007/978-3-642-40235-7_9</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-642-40234-0" title="Special:BookSources/978-3-642-40234-0"><bdi>978-3-642-40234-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Geodetic+Distance+Queries+on+R-Trees+for+Indexing+Geographic+Data&rft.btitle=Advances+in+Spatial+and+Temporal+Databases&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=146&rft.date=2013&rft_id=info%3Adoi%2F10.1007%2F978-3-642-40235-7_9&rft.isbn=978-3-642-40234-0&rft.aulast=Schubert&rft.aufirst=E.&rft.au=Zimek%2C+A.&rft.au=Kriegel%2C+H.+P.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-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 id="CITEREFMengbai_Xiao,_Hao_Wang,_Liang_Geng,_Rubao_Lee,_and_Xiaodong_Zhang2022" class="citation conference cs1">Mengbai Xiao, Hao Wang, Liang Geng, Rubao Lee, and Xiaodong Zhang (2022). <i>" An RDMA-enabled In-memory Computing Platform for R-tree on Clusters"</i>. ACM Transactions on Spatial Algorithms and Systems. pp. <span class="nowrap">1–</span>26. <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%2F3503513">10.1145/3503513</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=%22+An+RDMA-enabled+In-memory+Computing+Platform+for+R-tree+on+Clusters%22&rft.pages=%3Cspan+class%3D%22nowrap%22%3E1-%3C%2Fspan%3E26&rft.date=2022&rft_id=info%3Adoi%2F10.1145%2F3503513&rft.au=Mengbai+Xiao%2C+Hao+Wang%2C+Liang+Geng%2C+Rubao+Lee%2C+and+Xiaodong+Zhang&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_conference" title="Template:Cite conference">cite conference</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-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHwangKwonChaLee2003" class="citation book cs1">Hwang, S.; Kwon, K.; Cha, S. K.; Lee, B. S. (2003). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/advancesinspatia0000sstd/page/10">"Performance Evaluation of Main-Memory R-tree Variants"</a></span>. <i>Advances in Spatial and Temporal Databases</i>. Lecture Notes in Computer Science. Vol. 2750. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/advancesinspatia0000sstd/page/10">10</a>. <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%2F978-3-540-45072-6_2">10.1007/978-3-540-45072-6_2</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-40535-1" title="Special:BookSources/978-3-540-40535-1"><bdi>978-3-540-40535-1</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Performance+Evaluation+of+Main-Memory+R-tree+Variants&rft.btitle=Advances+in+Spatial+and+Temporal+Databases&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=10&rft.date=2003&rft_id=info%3Adoi%2F10.1007%2F978-3-540-45072-6_2&rft.isbn=978-3-540-40535-1&rft.aulast=Hwang&rft.aufirst=S.&rft.au=Kwon%2C+K.&rft.au=Cha%2C+S.+K.&rft.au=Lee%2C+B.+S.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fadvancesinspatia0000sstd%2Fpage%2F10&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-prtree-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-prtree_8-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFArgeDe_BergHaverkortYi2004" class="citation book cs1"><a href="/wiki/Lars_Arge" title="Lars Arge">Arge, L.</a>; De Berg, M.; Haverkort, H. J.; Yi, K. (2004). <a rel="nofollow" class="external text" href="http://www.win.tue.nl/~mdberg/Papers/prtree.pdf">"The Priority R-tree"</a> <span class="cs1-format">(PDF)</span>. <a rel="nofollow" class="external text" href="http://doi.acm.org/10.1145/1007568.1007608"><i>Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04</i></a>. p. 347. <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%2F1007568.1007608">10.1145/1007568.1007608</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1581138597" title="Special:BookSources/978-1581138597"><bdi>978-1581138597</bdi></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:6817500">6817500</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+Priority+R-tree&rft.btitle=Proceedings+of+the+2004+ACM+SIGMOD+international+conference+on+Management+of+data+%E2%80%93+SIGMOD+%2704&rft.pages=347&rft.date=2004&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A6817500%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F1007568.1007608&rft.isbn=978-1581138597&rft.aulast=Arge&rft.aufirst=L.&rft.au=De+Berg%2C+M.&rft.au=Haverkort%2C+H.+J.&rft.au=Yi%2C+K.&rft_id=http%3A%2F%2Fwww.win.tue.nl%2F~mdberg%2FPapers%2Fprtree.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrinkhoffKriegelSeeger1993" class="citation journal cs1">Brinkhoff, T.; <a href="/wiki/Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Kriegel, H. P.</a>; Seeger, B. (1993). "Efficient processing of spatial joins using R-trees". <i>ACM SIGMOD Record</i>. <b>22</b> (2): 237. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.4514">10.1.1.72.4514</a></span>. <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%2F170036.170075">10.1145/170036.170075</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:7810650">7810650</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+SIGMOD+Record&rft.atitle=Efficient+processing+of+spatial+joins+using+R-trees&rft.volume=22&rft.issue=2&rft.pages=237&rft.date=1993&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.72.4514%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A7810650%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F170036.170075&rft.aulast=Brinkhoff&rft.aufirst=T.&rft.au=Kriegel%2C+H.+P.&rft.au=Seeger%2C+B.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></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"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBöhmKrebs2003" class="citation book cs1">Böhm, Christian; Krebs, Florian (2003-09-01). "Supporting KDD Applications by the k-Nearest Neighbor Join". <i>Database and Expert Systems Applications</i>. Lecture Notes in Computer Science. Vol. 2736. Springer, Berlin, Heidelberg. pp. <span class="nowrap">504–</span>516. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.454">10.1.1.71.454</a></span>. <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%2F978-3-540-45227-0_50">10.1007/978-3-540-45227-0_50</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9783540408062" title="Special:BookSources/9783540408062"><bdi>9783540408062</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Supporting+KDD+Applications+by+the+k-Nearest+Neighbor+Join&rft.btitle=Database+and+Expert+Systems+Applications&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=%3Cspan+class%3D%22nowrap%22%3E504-%3C%2Fspan%3E516&rft.pub=Springer%2C+Berlin%2C+Heidelberg&rft.date=2003-09-01&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.71.454%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1007%2F978-3-540-45227-0_50&rft.isbn=9783540408062&rft.aulast=B%C3%B6hm&rft.aufirst=Christian&rft.au=Krebs%2C+Florian&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAchtertBöhmKröger2006" class="citation conference cs1">Achtert, Elke; Böhm, Christian; Kröger, Peer (2006). "DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking". In Ng, Wee Keong; Kitsuregawa, Masaru; Li, Jianzhong; Chang, Kuiyu (eds.). <i>Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings</i>. Lecture Notes in Computer Science. Vol. 3918. Springer. pp. <span class="nowrap">119–</span>128. <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%2F11731139_16">10.1007/11731139_16</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=DeLi-Clu%3A+Boosting+Robustness%2C+Completeness%2C+Usability%2C+and+Efficiency+of+Hierarchical+Clustering+by+a+Closest+Pair+Ranking&rft.btitle=Advances+in+Knowledge+Discovery+and+Data+Mining%2C+10th+Pacific-Asia+Conference%2C+PAKDD+2006%2C+Singapore%2C+April+9-12%2C+2006%2C+Proceedings&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=%3Cspan+class%3D%22nowrap%22%3E119-%3C%2Fspan%3E128&rft.pub=Springer&rft.date=2006&rft_id=info%3Adoi%2F10.1007%2F11731139_16&rft.aulast=Achtert&rft.aufirst=Elke&rft.au=B%C3%B6hm%2C+Christian&rft.au=Kr%C3%B6ger%2C+Peer&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKuanLewis1997" class="citation conference cs1">Kuan, J.; Lewis, P. (1997). "Fast k nearest neighbour search for R-tree family". <i>Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications (Cat. No.97TH8237)</i>. p. 924. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICICS.1997.652114">10.1109/ICICS.1997.652114</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-7803-3676-3" title="Special:BookSources/0-7803-3676-3"><bdi>0-7803-3676-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Fast+k+nearest+neighbour+search+for+R-tree+family&rft.btitle=Proceedings+of+ICICS%2C+1997+International+Conference+on+Information%2C+Communications+and+Signal+Processing.+Theme%3A+Trends+in+Information+Systems+Engineering+and+Wireless+Multimedia+Communications+%28Cat.+No.97TH8237%29&rft.pages=924&rft.date=1997&rft_id=info%3Adoi%2F10.1109%2FICICS.1997.652114&rft.isbn=0-7803-3676-3&rft.aulast=Kuan&rft.aufirst=J.&rft.au=Lewis%2C+P.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-greene-13"><span class="mw-cite-backlink">^ <a href="#cite_ref-greene_13-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-greene_13-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="CITEREFGreene1989" class="citation book cs1">Greene, D. (1989). "An implementation and performance analysis of spatial data access methods". <i>[1989] Proceedings. Fifth International Conference on Data Engineering</i>. pp. <span class="nowrap">606–</span>615. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICDE.1989.47268">10.1109/ICDE.1989.47268</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8186-1915-1" title="Special:BookSources/978-0-8186-1915-1"><bdi>978-0-8186-1915-1</bdi></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:7957624">7957624</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=An+implementation+and+performance+analysis+of+spatial+data+access+methods&rft.btitle=%5B1989%5D+Proceedings.+Fifth+International+Conference+on+Data+Engineering&rft.pages=%3Cspan+class%3D%22nowrap%22%3E606-%3C%2Fspan%3E615&rft.date=1989&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A7957624%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FICDE.1989.47268&rft.isbn=978-0-8186-1915-1&rft.aulast=Greene&rft.aufirst=D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-rstar-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-rstar_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-rstar_14-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="CITEREFBeckmannKriegelSchneiderSeeger1990" class="citation book cs1">Beckmann, N.; <a href="/wiki/Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Kriegel, H. P.</a>; Schneider, R.; Seeger, B. (1990). <a rel="nofollow" class="external text" href="http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf">"The R*-tree: an efficient and robust access method for points and rectangles"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the 1990 ACM SIGMOD international conference on Management of data – SIGMOD '90</i>. p. 322. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.3731">10.1.1.129.3731</a></span>. <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%2F93597.98741">10.1145/93597.98741</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0897913652" title="Special:BookSources/978-0897913652"><bdi>978-0897913652</bdi></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:11567855">11567855</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+R%2A-tree%3A+an+efficient+and+robust+access+method+for+points+and+rectangles&rft.btitle=Proceedings+of+the+1990+ACM+SIGMOD+international+conference+on+Management+of+data+%E2%80%93+SIGMOD+%2790&rft.pages=322&rft.date=1990&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.129.3731%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A11567855%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F93597.98741&rft.isbn=978-0897913652&rft.aulast=Beckmann&rft.aufirst=N.&rft.au=Kriegel%2C+H.+P.&rft.au=Schneider%2C+R.&rft.au=Seeger%2C+B.&rft_id=http%3A%2F%2Fdbs.mathematik.uni-marburg.de%2Fpublications%2FmyPapers%2F1990%2FBKSS90.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-ang-tan-15"><span class="mw-cite-backlink">^ <a href="#cite_ref-ang-tan_15-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-ang-tan_15-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="CITEREFAngTan1997" class="citation conference cs1">Ang, C. H.; Tan, T. C. (1997). "New linear node splitting algorithm for R-trees". In Scholl, Michel; Voisard, Agnès (eds.). <i>Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997</i>. Lecture Notes in Computer Science. Vol. 1262. Springer. pp. <span class="nowrap">337–</span>349. <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%2F3-540-63238-7_38">10.1007/3-540-63238-7_38</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=New+linear+node+splitting+algorithm+for+R-trees&rft.btitle=Proceedings+of+the+5th+International+Symposium+on+Advances+in+Spatial+Databases+%28SSD+%2797%29%2C+Berlin%2C+Germany%2C+July+15%E2%80%9318%2C+1997&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=%3Cspan+class%3D%22nowrap%22%3E337-%3C%2Fspan%3E349&rft.pub=Springer&rft.date=1997&rft_id=info%3Adoi%2F10.1007%2F3-540-63238-7_38&rft.aulast=Ang&rft.aufirst=C.+H.&rft.au=Tan%2C+T.+C.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-xtree2-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-xtree2_16-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBerchtoldKeimKriegel1996" class="citation journal cs1">Berchtold, Stefan; Keim, Daniel A.; <a href="/wiki/Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Kriegel, Hans-Peter</a> (1996). <a rel="nofollow" class="external text" href="http://www.dbs.ifi.lmu.de/Publikationen/Papers/x-tree.ps">"The X-Tree: An Index Structure for High-Dimensional Data"</a>. <i>Proceedings of the 22nd VLDB Conference</i>. Mumbai, India: <span class="nowrap">28–</span>39.</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+22nd+VLDB+Conference&rft.atitle=The+X-Tree%3A+An+Index+Structure+for+High-Dimensional+Data&rft.pages=%3Cspan+class%3D%22nowrap%22%3E28-%3C%2Fspan%3E39&rft.date=1996&rft.aulast=Berchtold&rft.aufirst=Stefan&rft.au=Keim%2C+Daniel+A.&rft.au=Kriegel%2C+Hans-Peter&rft_id=http%3A%2F%2Fwww.dbs.ifi.lmu.de%2FPublikationen%2FPapers%2Fx-tree.ps&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></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 id="CITEREFLeuteneggerEdgingtonLopez1997" class="citation web cs1">Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (February 1997). <a rel="nofollow" class="external text" href="https://archive.org/details/nasa_techdoc_19970016975">"STR: A Simple and Efficient Algorithm for R-Tree Packing"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=STR%3A+A+Simple+and+Efficient+Algorithm+for+R-Tree+Packing&rft.date=1997-02&rft.aulast=Leutenegger&rft.aufirst=Scott+T.&rft.au=Edgington%2C+Jeffrey+M.&rft.au=Lopez%2C+Mario+A.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fnasa_techdoc_19970016975&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLeeLee2003" class="citation web cs1">Lee, Taewon; Lee, Sukho (June 2003). <a rel="nofollow" class="external text" href="http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM_18.pdf">"OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree"</a> <span class="cs1-format">(PDF)</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=OMT%3A+Overlap+Minimizing+Top-down+Bulk+Loading+Algorithm+for+R-tree&rft.date=2003-06&rft.aulast=Lee&rft.aufirst=Taewon&rft.au=Lee%2C+Sukho&rft_id=http%3A%2F%2Fftp.informatik.rwth-aachen.de%2FPublications%2FCEUR-WS%2FVol-74%2Ffiles%2FFORUM_18.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AR-tree" class="Z3988"></span></span> </li> </ol></div></div> <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=R-tree&action=edit&section=13" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Commons-logo.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/12px-Commons-logo.svg.png" decoding="async" width="12" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/18px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/24px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></a></span> Media related to <a href="https://commons.wikimedia.org/wiki/Category:R-tree" class="extiw" title="commons:Category:R-tree">R-tree</a> at Wikimedia Commons</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_structures237" 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_structures237" 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 href="/wiki/B-tree" title="B-tree">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 class="mw-selflink selflink">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_structures216" 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_structures216" 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 href="/wiki/B-tree" title="B-tree">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 class="mw-selflink selflink">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 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"><style data-mw-deduplicate="TemplateStyles:r1038841319">.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}</style></div><div role="navigation" class="navbox authority-control" aria-label="Navbox600" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a>: National <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q1198051#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="R-stromy"><a rel="nofollow" class="external text" href="https://aleph.nkp.cz/F/?func=find-c&local_base=aut&ccl_term=ica=ph613265&CON_LNG=ENG">Czech Republic</a></span></span></li></ul></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" 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=R-tree&oldid=1192723243">https://en.wikipedia.org/w/index.php?title=R-tree&oldid=1192723243</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">Category</a>: <ul><li><a href="/wiki/Category:R-tree" title="Category:R-tree">R-tree</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_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_May_2023" title="Category:Articles needing additional references from May 2023">Articles needing additional references from May 2023</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_2023" title="Category:Articles with unsourced statements from October 2023">Articles with unsourced statements from October 2023</a></li><li><a href="/wiki/Category:Articles_to_be_expanded_from_October_2011" title="Category:Articles to be expanded from October 2011">Articles to be expanded from October 2011</a></li><li><a href="/wiki/Category:All_articles_to_be_expanded" title="Category:All articles to be expanded">All articles to be expanded</a></li><li><a href="/wiki/Category:Articles_to_be_expanded_from_June_2008" title="Category:Articles to be expanded from June 2008">Articles to be expanded from June 2008</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></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 30 December 2023, at 23:53<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=R-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" lang="en" 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"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div 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"> <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> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-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-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">R-tree</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>16 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </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-b766959bd-ghcss","wgBackendResponseTime":130,"wgPageParseReport":{"limitreport":{"cputime":"0.778","walltime":"0.954","ppvisitednodes":{"value":2354,"limit":1000000},"postexpandincludesize":{"value":93714,"limit":2097152},"templateargumentsize":{"value":1983,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":7,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":111564,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 818.386 1 -total"," 30.03% 245.724 1 Template:Reflist"," 17.56% 143.671 7 Template:Cite_book"," 12.98% 106.213 1 Template:CS-Trees"," 12.90% 105.552 2 Template:Navbox"," 10.83% 88.596 3 Template:Ambox"," 10.68% 87.400 1 Template:Gallery"," 10.42% 85.294 1 Template:More_citations_needed"," 10.18% 83.283 1 Template:Short_description"," 8.20% 67.123 1 Template:Infobox_data_structure"]},"scribunto":{"limitreport-timeusage":{"value":"0.542","limit":"10.000"},"limitreport-memusage":{"value":6953277,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-5b65fffc7d-4c5s5","timestamp":"20250213230228","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"R-tree","url":"https:\/\/en.wikipedia.org\/wiki\/R-tree","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1198051","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1198051","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":"2004-07-29T12:47:33Z","dateModified":"2023-12-30T23:53:45Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/6\/6f\/R-tree.svg","headline":"tree-based data structure, used to index spatial information"}</script> </body> </html>