1.about B-Tree

?Although most of the search trees are binary trees, there is a popular serach tree taht is not binary. this tree is known as a B-tree.
雖然大多數的查找樹是二叉樹，但是也存在不是二叉樹的查找樹。這種樹就是B-樹。簡言之，B樹是一種多路平衡查找樹。他適合在磁盤等直接存儲設備上組織動態的查找表。


A B-tree of order M is a tree with the following structural properties:
????(1) Theroot is either a leaf or has between 2 and M children.
????(2) All nodeleaf nodes(except the root) have between [M/2] and M children.
????(3) All leaves are at the same depth.
????(4) Each node should contain such data fields?
????????????????????(P0,K0,P1,K1,....Pi,Ki..Pm,Km)
????????????[K0,K1,...Km] is the increased key.
????????????[P0,P1,...Pm] is the pointer which is point to its related child nodes.
一棵m階(m>=3)的B樹具有如下性質：
????（1）根節點要么是葉子節點 或者有2到m 個孩子節點。
??????(2) 所有非葉子節點有 m/2到m個孩子節點。
???????(3)所有葉子節點都具有相同高度。
????????(4) 每個節點應含有以下數據域：
????????????(P0,K0,P1,K1,....Pi,Ki..Pm,Km)
??????????? 其中，?[K0,K1,...Km]?是遞增的關鍵字序列
?????????????????????[P0,P1,...Pm] 是指向其孩子節點的指針域，初始為空。

All data are stored at the leaves. Contained in each interios node are pointers P1,P2,...Pm to the children, and values k1,k2,...k(m-1),representing the smallest key found in the subtrees P2,P3,...,Pm,respectively. Of course, some of the these pointers might be NULL, and the corresponding Ki would then be undefined. For every node, all the keys in subtree P1 are smaller than the keys in subtree P2, and so on. The leaves contail all the actula data, whichare either the keys themselves or pointers to recores containing the keys. We will assume the former tokeep our examples simpe. There are various definitions of B-trees that change this structure in mostly minor ways, but this definition is one ot the popular forms. We will also insist that the number of keys in a leaf is also between?[M/2] and M.
所有數據存儲在葉子節點。在每個節點內部包含指向其孩子節點的指針P0,P1,P2...Pm，以及K0,K1,K2,...Km等值,這些值是相應的子樹P1,P2...P(m-1)的最小值。當然，這些節點指針Pi也可能是空值，其相應的Ki也是空值。對于每個節點，所有在子數P1中的鍵值都要小于子樹P2中的鍵值，其他子樹亦然。

下圖是一個典型的B 樹
The tree as following diagram showed is an example of a B-tree of order 4



A B-tree of order 4 is more popularly known as a 2-3-4 tree, and a B-tree of order 3 is know as? a 2-3 tree. we will describe the operation of B-trees by using the special case of 2-3 trees. our starting point is the 2-3 tree follows.
一棵4階B樹也可稱為2-3-4樹，但是通常稱為4階樹。 階為3的樹通常稱為2-3樹。下面我們以2-3樹為例。


We have drawn interior nodes(nonleaves) , which contain the two pieces of data for each node. A dash line as a second piece of information in an interior node indicates that the node has only tow children. Leaves are drawn in boxes, which contain the keys. The keys in the leaves are ordered. To perform a Find. we start at the root and branch in one of(at most) three directions, depending on the relation of the key we are looking for to the two (possibly one) values stored at the node
我們畫出了內部節點，每個節點包括兩塊數據，節點內部--表示該節點只有兩個孩子。方框內是葉子節點，在該節點里面包含鍵值，葉子節點里的鍵值都按序排列。為了進行查找，我們從根節點開始，然后根據存儲在節點中的兩個值與鍵值之間的關系，選擇相應的支樹。


To perform an Insert on a previously unseen key, X, we follow the path as though we were performing a Find. when we get to a leaf node, we have found the correct place to put X. Thus, to insert a node with key 18, we can just add it to a leaf without causing any violations of the 2-3 tree properties. The result is shown in the following figure.
為了執行一個插入未見鍵值X的操作，我們首先進行查找操作，然后找到其相應位置。當找到一個葉子節點后，我們就可以找到正確的位置來插入X。 例如，我們要插入一個鍵18，我們只需要將其插入節點即可，而不會破壞2-3樹的屬性。

Unfortunately, since a leaf can hold only two or three keys,this might not always be possible, If we now try to insert 1 into the tree, we find that the node where it belongs is already full. Placing our new key into this node would give it a fourth element, which is not allowed. This is can be solved by making two nodes of two keys each and adjusting the information in the parent.

不幸的是，因為一個葉子節點只能有2或者3個鍵值。但是如果我們要插入鍵值1，那么這個可能性就要被破壞了，因為要插入的節點鍵值已滿。如果將其插入作為第4個鍵值，很顯然是不允許的。那么，我們只需要在父節點中進行調整就可以了。


Unfortanately, this idea does not always work, as can be seen by an attempt to insert 19 into the current tree. If we make two nodes of two keys each, we obtain the following tree.


This tree has an internal node with four children, but we only allow three per node. The solution is simple, We merely split this node into two nodes with two children. of course, this node might be one of three children itself, and thus splitting it would create a probrem for its parent(which would now have four children), but we can keep on splitting nodes on the way up to the root until we either get to the root or find a node with only two children.

轉載于:https://www.cnblogs.com/Winston/archive/2008/04/28/1174943.html

總結

以上是生活随笔為你收集整理的B-Trees Concepts B-树介绍（都快忘了:))的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。