View source for B+ tree

{{Short description|An m-ary rooted tree}}
{{Multiple issues|
{{external links|date=October 2016}}
{{more citations needed|date=November 2012}}
}}

{{Infobox data structure
|name=B+ tree
|type=[[Tree (data structure)]]
|space_avg= O(''n'')
|space_worst= O(''n'')
|search_avg= O(log ''n'')
|search_worst= O(log ''n'')
|insert_avg= O(log ''n'')
|insert_worst= O(log ''n'')
|delete_avg= O(log ''n'')
|delete_worst= O(log ''n'')
}}

A '''B+ tree''' is an [[m-ary tree]] with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves.<ref name=Navathe>{{cite book|last=Navathe|first=Ramez Elmasri, Shamkant B.|title=Fundamentals of database systems|year=2010|publisher=Pearson Education|location=Upper Saddle River, N.J.|isbn=9780136086208|pages=652–660|edition=6th}}</ref> The root may be either a leaf or a node with two or more children.

A B+ tree can be viewed as a [[B-tree]] in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.

The primary value of a B+ tree is in storing data for efficient retrieval in a [[Block (data storage)|block-oriented]] storage context — in particular, [[filesystems]]. This is primarily because unlike [[binary search tree]]s, B+ trees have very high fanout (number of pointers to child nodes in a node,<ref name=Navathe /> typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.

==History==
{{see also|B-tree}}

There is no single paper introducing the B+ tree concept. Instead, the notion of maintaining all data in leaf nodes is repeatedly brought up as an interesting variant of the B-tree, which was introduced by R. Bayer and E. McCreight.<ref>{{cite book |first1=R. |last1=Bayer |first2=E. |last2=McCreight  |title=Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '70 |chapter=Organization and maintenance of large ordered indices |date=November 1970 |pages=107–141 |doi=10.1145/1734663.1734671 |isbn=978-1-4503-7941-0 |chapter-url=https://dl.acm.org/doi/abs/10.1145/1734663.1734671}}</ref> [[Douglas Comer]] notes in an early survey of B-trees (which also covers B+ trees) that the B+ tree was used in IBM's [[VSAM]] data access software, and refers to an IBM published article from 1973.<ref>{{cite journal | doi=10.1145/356770.356776 | title=Ubiquitous B-Tree | year=1979 | last1=Comer | first1=Douglas | journal=ACM Computing Surveys | volume=11 | issue=2 | pages=121–137 | s2cid=101673 | doi-access=free }}</ref>

==Structure==
{{see also|Graph (discrete mathematics)#Graph|Tree (data structure)#Terminology}}

=== Pointer structure ===
[[File:B+tree node format.png|thumb|304x304px|B+ tree node format where K=4. (p_i represents the pointers, k_i represents the search keys).]]
As with other trees, B+ trees can be represented as a collection of three types of nodes: ''root'', ''internal'' (a.k.a. interior), and ''leaf''. In B+ trees, the following properties are maintained for these nodes:

* If <math display="inline">k_i</math> exists in any node in a B+ tree, then <math>k_{i-1}</math> exists in that node where <math>i \ge 1</math>.
* All leaf nodes have the same number of ancestors (i.e., they are all at the same depth).

The pointer properties of nodes are summarized in the tables below:

* {{mvar|K}}: Maximum number of potential search keys for each node in a B+ tree. (this value is constant over the entire tree).
* <math>p_i</math>: The pointer at the zero-based node index <math>i</math>.
* <math>k_i</math>: The search key at the zero-based node index <math>i</math>.

{| class="wikitable"
|+Internal Node Pointer Structure
!<math> p_0</math> when <math>k_0</math> exists
!<math>p_i</math> when <math>k_{i-1}</math> and <math>k_i</math> exist
!<math>p_i</math> when <math>k_{i-1}</math> exists, and <math>k_i</math> does not exist
!<math>p_i</math> when <math>k_{i-1}</math> and <math>k_i</math> do not exist
|-
|Points to subtree in which all search keys are less than <math>k_0</math>.
|Points to subtree in which all search keys are greater than or equal to <math>k_{i-1}</math> and are less than <math>k_i</math>.
|Points to subtree in which all search keys are greater than or equal to <math>k_{i-1}</math>.
|Here, <math>p_i</math> is empty.
|}
{| class="wikitable"
|+Leaf Node Pointer Structure
!<math>p_i</math> when <math>k_i</math> exists
!<math>p_i</math> when <math>k_i</math> does not exist and <math>i \ne  K</math>
!<math>p_K</math>
|-
|Points to a record with a value equal to <math>k_i</math>.
|Here, <math>p_i</math> is empty.
|Points to the next leaf in the tree.
|}

=== Node bounds ===
The node bounds are summarized in the table below:
{| class="wikitable"
|-
! Node Type !! Min Number of Keys !! Max Number of Keys 
!Min Number of Child Nodes
!Max Number of Child Nodes
|-
| Root Node (when it is a leaf node) || 0 || <math> K </math>
|0
|0
|- 
| Root Node (when it is an internal node) || 1 || <math> K </math>
|2<ref name="Navathe" />
|<math> K + 1 </math>
|-
| Internal Node || <math> \lfloor K/2 \rfloor </math>|| <math> K </math>
|<math> \lceil (K + 1)/2 \rceil </math> <math>  \equiv \lfloor K / 2 \rfloor + 1 </math>
|<math> K + 1 </math>
|-
| Leaf Node || <math>  \lceil K / 2 \rceil </math>|| <math> K </math>
|0
|0
|}
<ref name="algorithms-pdf" /><ref>{{Cite book |last1=Silberschatz |first1=Abraham |title=Database system concepts |last2=Korth |first2=Henry F. |last3=Sudarshan |first3=S. |date=2020 |publisher=McGraw-Hill Education |isbn=978-1-260-08450-4 |edition=Seventh |location=New York, NY}}</ref>

===Intervals in internal nodes===
{{see also|comparability|total order|Partially ordered set#Intervals}}

[[File:Bplustree.png|thumb|400px|right|A simple B+ tree example linking the keys 1–7 to data values d<sub>1</sub>-d<sub>7</sub>. The linked list (red) allows rapid in-order traversal. This particular tree's branching factor is <math> b </math>=4. Both keys in leaf and internal nodes are colored gray here.]]

By definition, each value contained within the B+ tree is a key contained in exactly one leaf node. Each key is required to be directly [[comparability|comparable]] with every other key, which forms a [[total order]].<ref name=total-order>{{cite web |url=https://db.inf.uni-tuebingen.de/staticfiles/teaching/ss13/db2/db2-04-1up.pdf|title="Tree-Structured Indexing: ISAM and B+-trees"|last=Grust|first=Torsten|date=Summer 2013|website=Logo der Universität Tübingen Department of Computer Science: Database Systems|page=84|archive-url=https://web.archive.org/web/20201031195459/https://db.inf.uni-tuebingen.de/staticfiles/teaching/ss13/db2/db2-04-1up.pdf|archive-date=2020-10-31}}</ref> This enables each leaf node to keep all of its keys sorted at all times, which then enables each internal node to construct an ordered collection of [[Partially ordered set#Intervals|intervals]] representing the contiguous extent of values contained in a given leaf. Internal nodes higher in the tree can then construct their own intervals, which recursively aggregate the intervals contained in their own child internal nodes. Eventually, the root of a B+ Tree represents the whole range of values in the tree, where every internal node represents a subinterval.

For this recursive interval information to be retained, internal nodes must additionally contain <math>m - 1</math> copies of keys <math>l_i</math> for <math>i \in [1, m - 1]</math> representing the least element within the interval covered by the child with index {{mvar|i}} (which may itself be an internal node, or a leaf). Where {{mvar|m}} represents the ''actual'' number of children for a given internal node.

==Characteristics==
The ''order'' or ''[[branching factor]]'' {{mvar|b}} of a B+ tree measures the capacity of interior nodes, i.e. their maximum allowed number of direct child nodes. This value is constant over the entire tree. For a {{mvar|b}}-order B+ tree with {{mvar|h}} levels of index: {{citation needed|date=December 2016}}
* The maximum number of records stored is <math>n_{\max} = b^h - b^{h-1}</math>
* The minimum number of records stored is <math>n_{\min} = 2\left\lceil\tfrac{b}{2}\right\rceil^{h-1}-2\left\lceil\tfrac{b}{2}\right\rceil^{h-2}</math>
* The minimum number of keys is <math>n_\mathrm{kmin} = 2\left\lceil\tfrac{b}{2}\right\rceil^{h-1}-1</math>
* The maximum number of keys is <math>n_\mathrm{kmax} = b^h-1</math>
* The space required to store the tree is <math>O(n)</math>
* Inserting a record requires <math>O(\log_bn)</math> operations
* Finding a record requires <math>O(\log_bn)</math> operations
* Removing a (previously located) record requires <math>O(\log_bn)</math> operations
* Performing a [[range query]] with ''k'' elements occurring within the range requires <math>O(\log_bn+k)</math> operations
* The B+ tree structure expands/contracts as the number of [[Row (database)|records]] increases/decreases. There are no restrictions on the size of B+ trees. Thus, increasing usability of a [[Database|database system]].
* Any change in structure does not affect performance due to balanced tree properties.<ref name=":0">{{cite book | doi=10.1007/978-3-642-12098-5_15 | chapter=Scalable Splitting of Massive Data Streams | title=Database Systems for Advanced Applications | series=Lecture Notes in Computer Science | date=2010 | last1=Zeitler | first1=Erik | last2=Risch | first2=Tore | volume=5982 | pages=184–198 | isbn=978-3-642-12097-8 | chapter-url=http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-136403 }}</ref>
* The data is stored in the leaf nodes and more branching of internal nodes helps to reduce the tree's height, thus, reduce search time. As a result, it works well in secondary storage devices.<ref>{{cite book | doi=10.1007/978-3-642-12098-5_22 | chapter=Update Migration: An Efficient B+ Tree for Flash Storage | title=Database Systems for Advanced Applications | series=Lecture Notes in Computer Science | date=2010 | last1=Xu | first1=Chang | last2=Shou | first2=Lidan | last3=Chen | first3=Gang | last4=Yan | first4=Cheng | last5=Hu | first5=Tianlei | volume=5982 | pages=276–290 | isbn=978-3-642-12097-8 }}</ref>
* Searching becomes extremely simple because all records are stored only in the leaf node and are sorted sequentially in the linked list.
* We can retrieve range retrieval or partial retrieval using B+ tree. This is made easier and faster by traversing the tree structure. This feature makes B+ tree structure applied in many search methods.<ref name=":0" />

==Algorithms==

===Search===
We are looking for a value {{mvar|k}} in the B+ Tree. This means that starting from the root, we are looking for the leaf which may contain the value {{mvar|k}}. At each node, we figure out which internal node we should follow. An internal B+ Tree node has at most <math> m \le b </math>  children, where every one of them represents a different sub-interval. We select the corresponding child via a linear search of the {{mvar|m}} entries, then when we finally get to a leaf, we do a linear search of its {{mvar|n}} elements for the desired key. Because we only traverse one branch of all the children at each rung of the tree, we achieve <math>O(\log N)</math> runtime, where {{mvar|N}} is the total number of keys stored in the leaves of the B+ tree.<ref name=algorithms-pdf>{{cite web |url=https://www.cs.helsinki.fi/u/mluukkai/tirak2010/B-tree.pdf|title="B+ trees"|last=Pollari-Malmi|first=Kerttu|website=Computer Science, Faculty of Science, University of Helsinki|page=3|archive-url=https://web.archive.org/web/20210414050947/https://www.cs.helsinki.fi/u/mluukkai/tirak2010/B-tree.pdf|archive-date=2021-04-14}}</ref>

 '''function''' search(''k'', ''root'') '''is'''
     '''let''' leaf = leaf_search(k, root)
     '''for''' leaf_key '''in''' leaf.keys():
         '''if''' k = leaf_key:
              '''return''' true
     '''return''' false

 '''function''' leaf_search(''k'', ''node'') '''is'''
     '''if''' node is a leaf:
         '''return''' node
     '''let''' p = node.children()
     '''let''' l = node.left_sided_intervals()
     '''assert''' <math>|p| = |l| + 1</math>
     '''let''' m = p.len()
     '''for''' i '''from''' 1 '''to''' m - 1:
         '''if''' <math>k \le l[i]</math>:
             '''return''' leaf_search(k, p[i])
     '''return''' leaf_search(k, p[m])

Note that this pseudocode uses 1-based array indexing.

===Insertion===
* Perform a search to determine which node the new record should go into.
* If the node is not full (at most <math> b - 1 </math> entries after the insertion), add the record.
* Otherwise, ''before'' inserting the new record
** Split the node.
*** original node has <math>\lceil (K+1)/2 \rceil</math> items
*** new node has <math>\lfloor (K+1)/2 \rfloor</math> items
** Copy <math>\lceil (K+1)/2 \rceil</math>-th key to the parent, and insert the new node to the parent.
** Repeat until a parent is found that need not split.
** Insert the new record into the new node.
* If the root splits, treat it as if it has an empty parent and split as outlined above.
B+ trees grow at the root and not at the leaves.<ref name=Navathe />

===Bulk-loading===
Given a collection of data records, we want to create a B+ tree index on some key field. One approach is to insert each record into an empty tree. However, it is quite expensive, because each entry requires us to start from the root and go down to the appropriate leaf page. An efficient alternative is to use bulk-loading.
* The first step is to sort the data entries according to a search key in ascending order.
* We allocate an empty page to serve as the root, and insert a pointer to the first page of entries into it.
* When the root is full, we split the root, and create a new root page.
* Keep inserting entries to the right most index page just above the leaf level, until all entries are indexed.

Note :
* when the right-most index page above the leaf level fills up, it is split;
* this action may, in turn, cause a split of the right-most index page one step closer to the root;
* splits only occur on the right-most path from the root to the leaf level.<ref>{{Cite web|url=http://web.cs.ucdavis.edu/~green/courses/ecs165b-s10/Lecture6.pdf|title=ECS 165B: Database System Implementation Lecture 6|date=April 9, 2010|website=UC Davis CS department|pages=21–23}}</ref>

=== Deletion ===
The purpose of the delete algorithm is to remove the desired entry node from the tree structure. We [[Recursive definition|recursively]] call the delete algorithm on the appropriate node until no node is found. For each function call, we traverse along, using the index to navigate until we find the node, remove it, and then work back up to the root.

At entry L that we wish to remove:

- If L is at least half-full, done

- If L has only d-1 entries, try to re-distribute, borrowing from sibling (adjacent node with same parent as L).

           After the re-distribution of two sibling nodes happens, the parent node must be updated to reflect this change. The index key that points to the second sibling must take the smallest value of that node to be the index key.

- If re-distribute fails, merge L and sibling. After merging, the parent node is updated by deleting the index key that point to the deleted entry. In other words, if merge occurred, must delete entry (pointing to L or sibling) from parent of L.

Note: merge could propagate to root, which means decreasing height.<ref>{{Cite book |last=Ramakrishnan |first=Raghu |title=Database management systems |date=2003 |publisher=McGraw-Hill |author2=Johannes Gehrke |isbn=0-07-246563-8 |edition=3rd |location=Boston |oclc=49977005}}</ref>
[[File:B+-tree-remove-61.png|thumb|B+ tree deletion|none]]

==Implementation==
The leaves (the bottom-most index blocks) of the B+ tree are often linked to one another in a linked list; this makes range queries or an (ordered) iteration through the blocks simpler and more efficient (though the aforementioned upper bound can be achieved even without this addition). This does not substantially increase space consumption or maintenance on the tree. This illustrates one of the significant advantages of a B+tree over a B-tree; in a B-tree, since not all keys are present in the leaves, such an ordered linked list cannot be constructed. A B+tree is thus particularly useful as a [[database index|database system index]], where the data typically resides on disk, as it allows the B+tree to actually provide an efficient structure for housing the data itself (this is described in<ref name="DMS" />{{rp|238}} as index structure "Alternative 1").

If a storage system has a block size of B bytes, and the keys to be stored have a size of k, arguably the most efficient B+ tree is one where <math>b=\tfrac B k -1</math>. Although theoretically the one-off is unnecessary, in practice there is often a little extra space taken up by the index blocks (for example, the linked list references in the leaf blocks). Having an index block which is slightly larger than the storage system's actual block represents a significant performance decrease; therefore erring on the side of caution is preferable.

If nodes of the B+ tree are organized as arrays of elements, then it may take a considerable time to insert or delete an element as half of the array will need to be shifted on average. To overcome this problem, elements inside a node can be organized in a binary tree or a B+ tree instead of an array.

B+ trees can also be used for data stored in RAM. In this case a reasonable choice for block size would be the size of processor's cache line.

Space efficiency of B+ trees can be improved by using some compression techniques. One possibility is to use [[delta encoding]] to compress keys stored into each block. For internal blocks, space saving can be achieved by either compressing keys or pointers. For string keys, space can be saved by using the following technique: Normally the ''i''-th entry of an internal block contains the first key of block {{tmath|i+1}}. Instead of storing the full key, we could store the shortest prefix of the first key of block {{tmath|i+1}} that is strictly greater (in lexicographic order) than last key of block ''i''. There is also a simple way to compress pointers: if we suppose that some consecutive blocks {{tmath|i, i+1, ... i+k}} are stored contiguously, then it will suffice to store only a pointer to the first block and the count of consecutive blocks.

All the above compression techniques have some drawbacks. First, a full block must be decompressed to extract a single element. One technique to overcome this problem is to divide each block into sub-blocks and compress them separately. In this case searching or inserting an element will only need to decompress or compress a sub-block instead of a full block. Another drawback of compression techniques is that the number of stored elements may vary considerably from a block to another depending on how well the elements are compressed inside each block.

== Applications ==
=== Filesystems ===

<!-- !!!!!
 DO NOT add entries here which use regular B-tree indexes. Note that
 shady sources (blogs etc) are unreliable, as many confuse B-trees with B+ trees.
 For instance, MySQL, PostgreSQL and Firebird only support B-trees.
!!!!! -->
The [[ReiserFS]], [[Novell Storage Services|NSS]], [[XFS]], [[JFS (file system)|JFS]], [[ReFS]], and [[Be File System|BFS]] filesystems all use this type of tree for metadata indexing; BFS also uses B+ trees for storing directories. [[NTFS]] uses B+ trees for directory and security-related metadata indexing. EXT4 uses extent trees (a modified B+ tree data structure) for file extent indexing.<ref name="practical-book">{{cite book | last=Giampaolo | first=Dominic | year=1999 | url=http://www.nobius.org/~dbg/practical-file-system-design.pdf | title=Practical File System Design with the Be File System | publisher=Morgan Kaufmann | isbn=1-55860-497-9 | access-date=2014-07-29 | archive-url=https://web.archive.org/web/20170213221835/http://www.nobius.org/~dbg/practical-file-system-design.pdf | archive-date=2017-02-13 | url-status=dead }}</ref> [[APFS]] uses B+ trees to store mappings from filesystem object IDs to their locations on disk, and to store filesystem records (including directories), though these trees' leaf nodes lack sibling pointers.<ref>{{Cite book|url=https://developer.apple.com/support/downloads/Apple-File-System-Reference.pdf|title=Apple File System Reference|date=2020-06-22|publisher=Apple Inc.|page=122|chapter=B-Trees|access-date=2021-03-10}}</ref>

=== Database Systems ===

[[Relational database management system]]s such as [[IBM Db2]],<ref name="DMS">Ramakrishnan Raghu, Gehrke Johannes – Database Management Systems, McGraw-Hill Higher Education (2000), 2nd edition (en) page 267</ref> [[Informix]],<ref name="DMS" /> [[Microsoft SQL Server]],<ref name="DMS" /> [[Oracle Database|Oracle 8]],<ref name="DMS" /> [[Adaptive Server Enterprise|Sybase ASE]],<ref name="DMS" /> and [[SQLite]]<ref name="SQLite">[http://sqlite.org/version3.html SQLite Version 3 Overview]</ref> support this type of tree for table indices, though each such system implements the basic B+ tree structure with variations and extensions.  Many [[NoSQL]] database management systems such as [[CouchDB]]<ref name="CouchDB">[http://guide.couchdb.org/draft/btree.html CouchDB Guide (see note after 3rd paragraph)]</ref> and [[Tokyo Cabinet]]<ref name="TC">[http://1978th.net/tokyocabinet/ Tokyo Cabinet reference] {{webarchive |url=https://web.archive.org/web/20090912082150/http://1978th.net/tokyocabinet/ |date=September 12, 2009 }}</ref> also support this type of tree for data access and storage.

Finding objects in a [[High-dimensional statistics|high-dimensional database]] that are comparable to a particular query object is one of the most often utilized and yet expensive procedures in such systems.{{citation needed|date=June 2022}} In such situations, finding the closest neighbor using a B+ tree is productive.<ref>{{Cite book |title=Database Systems for Advanced Applications |year=2010 |location=Japan}}</ref>

==== iDistance ====
{{further|iDistance}}

B+ tree is efficiently used to construct an indexed search method called iDistance. iDistance searches for k nearest neighbors (kNN) in high-dimension metric spaces. The data in those high-dimension spaces is divided based on space or partition strategies, and each partition has an index value that is close with the respect to the partition. From here, those points can be efficiently implemented using B+ tree, thus, the queries are mapped to single dimensions ranged search. In other words, the iDistance technique can be viewed as a way of accelerating the sequential scan. Instead of scanning records from the beginning to the end of the data file, the iDistance starts the scan from spots where the nearest neighbors can be obtained early with a very high probability.<ref>{{Cite journal |last1=Jagadish |first1=H. V. |last2=Ooi |first2=Beng Chin |last3=Tan |first3=Kian-Lee |last4=Yu |first4=Cui |last5=Zhang |first5=Rui |date=June 2005 |title=iDistance: An adaptive B+-tree based indexing method for nearest neighbor search |url=https://dl.acm.org/doi/10.1145/1071610.1071612 |journal=ACM Transactions on Database Systems |language=en |volume=30 |issue=2 |pages=364–397 |doi=10.1145/1071610.1071612 |s2cid=967678 |issn=0362-5915|url-access=subscription }}</ref>

==== NVRAM ====
{{further|Non-volatile random-access memory}}

Nonvolatile random-access memory (NVRAM) has been using B+ tree structure as the main memory access technique for the Internet Of Things (IoT) system because of its non static power consumption and high solidity of cell memory.  B+ can regulate the trafficking of data to memory efficiently. Moreover, with advanced strategies on frequencies of some highly used leaf or reference point, the B+ tree shows significant results in increasing the endurance of database systems.<ref>{{Cite journal |last1=Dharamjeet |last2=Chen |first2=Tseng-Yi |last3=Chang |first3=Yuan-Hao |last4=Wu |first4=Chun-Feng |last5=Lee |first5=Chi-Heng |last6=Shih |first6=Wei-Kuan |date=December 2021 |title=Beyond Write-Reduction Consideration: A Wear-Leveling-Enabled B⁺-Tree Indexing Scheme Over an NVRAM-Based Architecture |url=https://ieeexplore.ieee.org/document/9314895 |journal=IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |volume=40 |issue=12 |pages=2455–2466 |doi=10.1109/TCAD.2021.3049677 |s2cid=234157183 |issn=0278-0070|url-access=subscription }}</ref>

==See also==
* [[Binary search tree]]
* [[B-tree]]
* [[Divide-and-conquer algorithm]]

==References==
<references />

==External links==
{{wikibooks|Algorithm Implementation/Trees/B+ tree}}
{{External links|date=January 2019}}
* [https://pypi.python.org/pypi/blist B+ tree in Python, used to implement a list]
* [https://web.archive.org/web/20080723122307/http://www.cecs.csulb.edu/%7emonge/classes/share/B+TreeIndexes.html Dr. Monge's B+ Tree index notes]
* [http://blogs.ubc.ca/lrashid/files/2011/01/CCECE07.pdf Evaluating the performance of CSB+-trees on Mutithreaded Architectures]
* [http://www.cs.wisc.edu/~jignesh/publ/cci.pdf Effect of node size on the performance of cache conscious B+-trees]
* [https://web.archive.org/web/20070928103850/http://www.pittsburgh.intel-research.net/people/gibbons/papers/fpbptrees.pdf Fractal Prefetching B+-trees]
* [http://leo.saclay.inria.fr/events/EXPDB2006/PAPERS/Jonsson.pdf Towards pB+-trees in the field: implementations Choices and performance]
* [https://helda.helsinki.fi/bitstream/handle/10138/21429/cachecon.pdf Cache-Conscious Index Structures for Main-Memory Databases]
* [http://supertech.csail.mit.edu/cacheObliviousBTree.html Cache Oblivious B(+)-trees]
* [http://guide.couchdb.org/draft/btree.html The Power of B-Trees: CouchDB B+ Tree Implementation]
* [http://www.cs.usfca.edu/~galles/visualization/BPlusTree.html B+ Tree Visualization]
* [https://www.cs.helsinki.fi/u/mluukkai/tirak2010/B-tree.pdf B +-trees by Kerttu Pollari-Malmi]
* [https://courses.cs.washington.edu/courses/cse326/08sp/lectures/11-b-trees.pdf Data Structures B-Trees and B+ Trees]

===Implementations===
* [http://www.amittai.com/prose/bplustree.html Interactive B+ Tree Implementation in C]
* [http://www.amittai.com/prose/bplustree_cpp.html Interactive B+ Tree Implementation in C++]
* [http://idlebox.net/2007/stx-btree/ Memory based B+ tree implementation as C++ template library]
* [https://panthema.net/tlx/ 2019 improvement of previous]
* [https://web.archive.org/web/20120114231253/http://gitorious.org/bp-tree/main Stream based B+ tree implementation as C++ template library]
* [http://blog.conquex.com/?p=84 Open Source JavaScript B+ Tree Implementation]
* [https://metacpan.org/module/Tree::BPTree Perl implementation of B+ trees]
* [http://bplusdotnet.sourceforge.net Java/C#/Python implementations of B+ trees]
*[http://core.loyc.net/collections/alists-part2 C# B+ tree and related "A-List" data structures]
* [http://csharptest.net/?page_id=563 File based B+Tree in C# with threading and MVCC support]
* [https://www.npmjs.com/package/sorted-btree Fast semi-persistent in-memory B+ Tree in TypeScript/JavaScript, MIT License]
* [http://prosehack.wordpress.com/2012/05/25/a-javascript-b-tree/ JavaScript B+ Tree, MIT License]
* [http://goneill.co.nz/btree.php JavaScript B+ Tree, Interactive and Open Source]

{{CS-Trees}}

{{DEFAULTSORT:B plus Tree}}
[[Category:B-tree]]
[[Category:1972 in computing]]
[[Category:Computer-related introductions in 1972]]