{"id":2445,"date":"2014-06-18T16:00:08","date_gmt":"2014-06-18T20:00:08","guid":{"rendered":"http:\/\/sqlity.net\/en\/?p=2445"},"modified":"2014-11-13T13:37:09","modified_gmt":"2014-11-13T18:37:09","slug":"b-plus-tree","status":"publish","type":"post","link":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/","title":{"rendered":"B+Trees – How SQL Server Indexes are Stored on Disk"},"content":{"rendered":"
\n

Introduction<\/h3>\n

\nSQL Server organizes indexes in a structure known as B+Tree. Many think, B+Trees are binary trees. However, that is not correct. A binary tree is a hierarchical structure organizing nodes (table rows) in a manner that allows searches to be executed extremely efficiently. On the flipside, the binary tree structure is very volatile when it comes to updates, often requiring the entire structure to be rebuilt when a single data point was changed. (See Wikipedia<\/a> for more details.) That makes binary tree a very poor choice when it comes to persisting data on disk.\n<\/p>\n

The B-Tree<\/h3>\n

\nIn 1972, Rudolf Bayer and Ed McCreight, both working at Boeing at the time, were looking for a way to overcome some of the shortfalls of the binary tree. Their solution was the B-Tree<\/a>. The main difference between a binary tree and a B-Tree is that the latter allows for more than one data point (table row) per node. B-Trees are also balanced, which means that the time it takes to execute a search within this structure is mostly independent of the value to be found.\n<\/p>\n

\nFor a long time it was unclear what the \"B\" in the name represented. Candidates discussed in public where \"Boeing\", \"Bayer\", \"Balanced\", \"Bushy\" and others. In 2013, the B-Tree had just turned 40, Ed McCreight revealed in an interview, that they intentionally never published an answer to this question. They were thinking about many of these options themselves at the time and decided to just leave it an open question.\n<\/p>\n

The B+Tree<\/h3>\n

\nB-Trees are a lot more efficient than binary trees when it comes to updates, but some operations can still turn out expensive, depending on where the node that will hold the new or updated data lives in the tree. Therefore, another optimization was made to B-Trees to help with this problem. Instead of treating all nodes equal, the new structure has two types of nodes. The lowest level nodes, also called leaf nodes, hold the actual data. All other nodes including the root node only hold the key values and pointers to the next nodes. This type of tree is called a B+Tree and you can see an example below:\n<\/p>\n

\n\"A<\/a>\n<\/p>\n

\nThere are no limitations on the number of key-pointer-pairs or data rows within a node. The only limitation is that all leaf nodes have the same distance from the root node. That means that the work to seek for a particular data point is always the same, no matter what the key value is. It also keeps updates very localized in the tree. I might have to move a few rows to a new node during an update but then I probably only need to change a single parent node to integrate that new node. It is however possible for a single change to affect every level of the tree, but those changes are rare. You can find more information about B+Trees here<\/a>.\n<\/p>\n

B+Trees in SQL Server<\/h3>\n

\nSQL Server stores its indexes in B+Tree format. There are a few exceptions - for example temporary hash indexes, created during a hash join operation, or column store indexes, which are not really indexes at all. However, all key-based clustered and non-clustered persisted SQL Server indexes are organized and stored as B+Trees.\n<\/p>\n

\nEach node in such a tree is a page in SQL Server terms and you will find two page types in each index. The first type are the data pages (pages of type 1)<\/a>. Each leaf level node in a SQL Server B+Tree index is a single data page. The second type are intermediate index pages (pages of type 2). Each node in an index B+Tree that is not a leaf level node is a single page of type 2. Those pages contain rows just like the data pages. But in addition they contain a pointer for each row that identifies the next child page. That child page can be either of type 1 or of type 2, depending on the location in the B+Tree.\n<\/p>\n

Summary<\/h3>\n

\nSQL Server stores key-based persisted indexes in the form of a B+Tree. Each node in such a tree is represented by a single page. Data pages build the leaf level of the tree while all other nodes are made of single pages of type 2.\n<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

How does SQL Server organize clustered and non-clustered indexes on disk? SQL server uses B+Trees. Read on to find out what B+Trees are and how they are implemented in SQL Server.<\/p>\n

[more…]<\/a><\/p>\n","protected":false},"author":3,"featured_media":2446,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[5,27,14,105],"tags":[195,196,194,115,106,107,15,109,193],"class_list":["post-2445","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-general","category-series","category-sql-server-internals","category-storage-wednesday","tag-b-tree","tag-btree","tag-binary-tree","tag-index","tag-internals","tag-page","tag-sql-server","tag-storage-engine","tag-tree"],"acf":[],"yoast_head":"\nB+Trees - How SQL Server Indexes are Stored on Disk - sqlity.net<\/title>\n<meta name=\"description\" content=\"How does SQL Server organize clustered and non-clustered indexes on disk? B+Trees. Read on to find out about B+Trees and their implementation in SQL Server.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"B+Trees - How SQL Server Indexes are Stored on Disk - sqlity.net\" \/>\n<meta property=\"og:description\" content=\"How does SQL Server organize clustered and non-clustered indexes on disk? B+Trees. Read on to find out about B+Trees and their implementation in SQL Server.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/\" \/>\n<meta property=\"og:site_name\" content=\"sqlity.net\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/sqlity.net\" \/>\n<meta property=\"article:published_time\" content=\"2014-06-18T20:00:08+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2014-11-13T18:37:09+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/sqlity.net\/wp-content\/uploads\/2014\/06\/B+Tree.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"960\" \/>\n\t<meta property=\"og:image:height\" content=\"720\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Sebastian Meine\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@sqlity\" \/>\n<meta name=\"twitter:site\" content=\"@sqlity\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Sebastian Meine\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/\"},\"author\":{\"name\":\"Sebastian Meine\",\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/#\\\/schema\\\/person\\\/bcffd8c572bc2f1bd10fdba80135e53c\"},\"headline\":\"B+Trees – How SQL Server Indexes are Stored on Disk\",\"datePublished\":\"2014-06-18T20:00:08+00:00\",\"dateModified\":\"2014-11-13T18:37:09+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/\"},\"wordCount\":729,\"commentCount\":8,\"image\":{\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/sqlity.net\\\/wp-content\\\/uploads\\\/2014\\\/06\\\/B+Tree.jpg\",\"keywords\":[\"b-tree\",\"B+Tree\",\"binary tree\",\"Index\",\"internals\",\"page\",\"SQL Server\",\"storage engine\",\"tree\"],\"articleSection\":[\"General\",\"Series\",\"SQL Server Internals\",\"Storage Wednesday\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/\",\"url\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/\",\"name\":\"B+Trees - How SQL Server Indexes are Stored on Disk - sqlity.net\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/sqlity.net\\\/wp-content\\\/uploads\\\/2014\\\/06\\\/B+Tree.jpg\",\"datePublished\":\"2014-06-18T20:00:08+00:00\",\"dateModified\":\"2014-11-13T18:37:09+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/#\\\/schema\\\/person\\\/bcffd8c572bc2f1bd10fdba80135e53c\"},\"description\":\"How does SQL Server organize clustered and non-clustered indexes on disk? B+Trees. Read on to find out about B+Trees and their implementation in SQL Server.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/#primaryimage\",\"url\":\"https:\\\/\\\/sqlity.net\\\/wp-content\\\/uploads\\\/2014\\\/06\\\/B+Tree.jpg\",\"contentUrl\":\"https:\\\/\\\/sqlity.net\\\/wp-content\\\/uploads\\\/2014\\\/06\\\/B+Tree.jpg\",\"width\":960,\"height\":720,\"caption\":\"A B+Tree Example\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/2445\\\/b-plus-tree\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/sqlity.net\\\/en\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"B+Trees – How SQL Server Indexes are Stored on Disk\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/#website\",\"url\":\"https:\\\/\\\/sqlity.net\\\/en\\\/\",\"name\":\"sqlity.net\",\"description\":\"Quality for SQL\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/sqlity.net\\\/en\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/sqlity.net\\\/en\\\/#\\\/schema\\\/person\\\/bcffd8c572bc2f1bd10fdba80135e53c\",\"name\":\"Sebastian Meine\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/4ab0a6d02dd494849a584a2c3c8bc3bdcef1d0aa5f87e98bf905dbdb9ad2ce3a?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/4ab0a6d02dd494849a584a2c3c8bc3bdcef1d0aa5f87e98bf905dbdb9ad2ce3a?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/4ab0a6d02dd494849a584a2c3c8bc3bdcef1d0aa5f87e98bf905dbdb9ad2ce3a?s=96&d=mm&r=g\",\"caption\":\"Sebastian Meine\"},\"sameAs\":[\"http:\\\/\\\/sqlity.net\",\"https:\\\/\\\/x.com\\\/sqlity\"]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"B+Trees - How SQL Server Indexes are Stored on Disk - sqlity.net","description":"How does SQL Server organize clustered and non-clustered indexes on disk? B+Trees. Read on to find out about B+Trees and their implementation in SQL Server.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/","og_locale":"en_US","og_type":"article","og_title":"B+Trees - How SQL Server Indexes are Stored on Disk - sqlity.net","og_description":"How does SQL Server organize clustered and non-clustered indexes on disk? B+Trees. Read on to find out about B+Trees and their implementation in SQL Server.","og_url":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/","og_site_name":"sqlity.net","article_publisher":"https:\/\/www.facebook.com\/sqlity.net","article_published_time":"2014-06-18T20:00:08+00:00","article_modified_time":"2014-11-13T18:37:09+00:00","og_image":[{"width":960,"height":720,"url":"https:\/\/sqlity.net\/wp-content\/uploads\/2014\/06\/B+Tree.jpg","type":"image\/jpeg"}],"author":"Sebastian Meine","twitter_card":"summary_large_image","twitter_creator":"@sqlity","twitter_site":"@sqlity","twitter_misc":{"Written by":"Sebastian Meine","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/#article","isPartOf":{"@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/"},"author":{"name":"Sebastian Meine","@id":"https:\/\/sqlity.net\/en\/#\/schema\/person\/bcffd8c572bc2f1bd10fdba80135e53c"},"headline":"B+Trees – How SQL Server Indexes are Stored on Disk","datePublished":"2014-06-18T20:00:08+00:00","dateModified":"2014-11-13T18:37:09+00:00","mainEntityOfPage":{"@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/"},"wordCount":729,"commentCount":8,"image":{"@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/sqlity.net\/wp-content\/uploads\/2014\/06\/B+Tree.jpg","keywords":["b-tree","B+Tree","binary tree","Index","internals","page","SQL Server","storage engine","tree"],"articleSection":["General","Series","SQL Server Internals","Storage Wednesday"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/","url":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/","name":"B+Trees - How SQL Server Indexes are Stored on Disk - sqlity.net","isPartOf":{"@id":"https:\/\/sqlity.net\/en\/#website"},"primaryImageOfPage":{"@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/#primaryimage"},"image":{"@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/sqlity.net\/wp-content\/uploads\/2014\/06\/B+Tree.jpg","datePublished":"2014-06-18T20:00:08+00:00","dateModified":"2014-11-13T18:37:09+00:00","author":{"@id":"https:\/\/sqlity.net\/en\/#\/schema\/person\/bcffd8c572bc2f1bd10fdba80135e53c"},"description":"How does SQL Server organize clustered and non-clustered indexes on disk? B+Trees. Read on to find out about B+Trees and their implementation in SQL Server.","breadcrumb":{"@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/#primaryimage","url":"https:\/\/sqlity.net\/wp-content\/uploads\/2014\/06\/B+Tree.jpg","contentUrl":"https:\/\/sqlity.net\/wp-content\/uploads\/2014\/06\/B+Tree.jpg","width":960,"height":720,"caption":"A B+Tree Example"},{"@type":"BreadcrumbList","@id":"https:\/\/sqlity.net\/en\/2445\/b-plus-tree\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/sqlity.net\/en\/"},{"@type":"ListItem","position":2,"name":"B+Trees – How SQL Server Indexes are Stored on Disk"}]},{"@type":"WebSite","@id":"https:\/\/sqlity.net\/en\/#website","url":"https:\/\/sqlity.net\/en\/","name":"sqlity.net","description":"Quality for SQL","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/sqlity.net\/en\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/sqlity.net\/en\/#\/schema\/person\/bcffd8c572bc2f1bd10fdba80135e53c","name":"Sebastian Meine","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/4ab0a6d02dd494849a584a2c3c8bc3bdcef1d0aa5f87e98bf905dbdb9ad2ce3a?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/4ab0a6d02dd494849a584a2c3c8bc3bdcef1d0aa5f87e98bf905dbdb9ad2ce3a?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/4ab0a6d02dd494849a584a2c3c8bc3bdcef1d0aa5f87e98bf905dbdb9ad2ce3a?s=96&d=mm&r=g","caption":"Sebastian Meine"},"sameAs":["http:\/\/sqlity.net","https:\/\/x.com\/sqlity"]}]}},"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/sqlity.net\/wp-content\/uploads\/2014\/06\/B+Tree.jpg","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p2wXuw-Dr","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/posts\/2445","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/comments?post=2445"}],"version-history":[{"count":0,"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/posts\/2445\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/media\/2446"}],"wp:attachment":[{"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/media?parent=2445"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/categories?post=2445"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sqlity.net\/en\/wp-json\/wp\/v2\/tags?post=2445"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}