B樹和B+樹

03-01

簡介

在計算機科學中，B樹（英語：B-tree）是一種自平衡的樹，能夠保持數據有序。這種數據結構能夠讓查找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。B樹，概括來說是一個一般化的二叉查找樹（binary search tree），可以擁有多於2個子節點。與自平衡二叉查找樹不同，B樹為系統大塊數據的讀寫操作做了優化。B樹減少定位記錄時所經歷的中間過程，從而加快存取速度。B樹這種數據結構可以用來描述外部存儲。這種數據結構常被應用在資料庫和文件系統的實現上。

定義

`B-Tree is a self-balanced search tree with multiple keys in every node and more than two children for every node.`

B樹是一種自平衡的搜索樹,每一個節點node都有多個keys，並且每個節點有2個子節點或者多於2個子節點。

A B+ tree is an N-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves.The root may be either a leaf or a node with two or more children

B+樹是一個n叉排序樹，通常每個節點有多個孩子，一棵B+樹包含一個根節點、多個內部節點和葉子節點。根節點可能是一個葉子節點，也可能是一個包含兩個或兩個以上孩子節點的節點。

特徵

B-Tree of Order m has the following properties…

Property #1 - All the leaf nodes must be at same level.
Property #2 - All nodes except root must have at least [m/2]-1 keys and maximum of m-1 keys.
Property #3 - All non leaf nodes except root (i.e. all internal nodes) must have at least m/2 children.
Property #4 - If the root node is a non leaf node, then it must have at least 2 children.
Property #5 - A non leaf node with n-1 keys must have n number of children.
Property #6 - All the key values within a node must be in Ascending Order.

搜尋方法

In a B-Ttree, the search operation is similar to that of Binary Search Tree. In a Binary search tree, the search process starts from the root node and every time we make a 2-way decision (we go to either left subtree or right subtree). In B-Tree also search process starts from the root node but every time we make n-way decision where n is the total number of children that node has. In a B-Ttree, the search operation is performed with O(log n) time complexity. The search operation is performed as follows…

Step 1: Read the search element from the user
Step 2: Compare, the search element with first key value of root node in the tree.
Step 3: If both are matching, then display 「Given node found!!!」 and terminate the function
Step 4: If both are not matching, then check whether search element is smaller or larger than that key value.
Step 5: If search element is smaller, then continue the search process in left subtree.
Step 6: If search element is larger, then compare with next key value in the same node and repeate step 3, 4, 5 and 6 until we found exact match or comparision completed with last key value in a leaf node.
Step 7: If we completed with last key value in a leaf node, then display 「Element is not found」 and terminate the function.

大致的意思就是查詢的條件A,和root節點值比較，如果相等則success,不相等則判斷是否小於該節點，小於則查詢左子樹，大於則查詢此時節點的下一個值，以此類推，直到此時節點最後一個值還是小於A,則查詢右子樹，直到找到或者結束查找。

插入方法

Insertion Operation in B-Tree In a B-Tree, the new element must be added only at leaf node. That means, always the new keyValue is attached to leaf node only. The insertion operation is performed as follows…

Step 1: Check whether tree is Empty.
Step 2: If tree is Empty, then create a new node with new key value and insert into the tree as a root node.
Step 3: If tree is Not Empty, then find a leaf node to which the new key value cab be added using Binary Search Tree logic.
Step 4: If that leaf node has an empty position, then add the new key value to that leaf node by maintaining ascending order of key value within the node.
Step 5: If that leaf node is already full, then split that leaf node by sending middle value to its parent node. Repeat tha same until sending value is fixed into a node.
Step 6: If the spilting is occuring to the root node, then the middle value becomes new root node for the tree and the height of the tree is increased by one.

刪除方法

參考8的鏈接,有圖有真相，這裡就摘錄一些重點文字條件吧。

k：刪除的值


 
x: k所在的節點
x.n: k所在節點的長度
t: k所在節點的層級

If k is in the node x which is a leaf and x.n>=t, Here you can straightaway delete k from x.
If k is in the node x which is a leaf and x.n == (t-1)

Find the immediate sibling y of x, the extreme key m of y, the parent p of x and the parent key l of k

If y.n >= t:
    Move l into x
    Move m into p
    Delete k from x

Find the immediate sibling y of x, the extreme key m of y, the parent p of x and the parent key l of k

If y.n == t-1:
    Merge x and y
    Move down l to the new node as the median key
    Delete k from the new node

If k is in the node x and x is an internal node (not a leaf)

Find the child node y that precedes k (the node which is on the left side of k)

If y.n >= t:
    Find the key k』 in y which is the predecessor of k
    Delete k』 recursively. (Here k』 can be another internal node as well. So we have to delete it recursively in the same way)

 
    Replace k with k』 in x

Find the child node y that precedes k

If y.n < t (or y.n == (t-1)):
    Find the child node z that follows k (the node which is on the right side of k)
    If z.n >= t:
        Find k』』 in z which is the successor of k
        Delete k』』 recursively
        Replace k with k』』 in x

Find the child node y that precedes k and the child node z that follows k

If y.n == (t-1) AND z.n == (t-1):
    Merge k and z to y
    Free memory of node z
    Recursively delete k from y

B-樹和B+樹區別

B和B+樹的區別在於，B+樹的非葉子結點只包含key信息，不包含data，每個節點的指針上限為2t而不是2t+1.所有的葉子結點和相連的節點使用鏈表相連，便於區間查找和遍歷。

綜述

磁碟存儲和mysql的索引這一塊用的比較多，以空間換時間來提升查找速度。（圖片基本是從參考鏈接那邊拿過來的，站在前人的肩膀上。）

參考

https://zh.wikipedia.org/wiki/B%E6%A0%91
http://blog.codinglabs.org/articles/theory-of-mysql-index.html
http://btechsmartclass.com/DS/U5_T3.html
http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html
https://www.geeksforgeeks.org/b-tree-set-1-introduction-2/
https://www.geeksforgeeks.org/b-tree-set-1-insert-2/
https://www.geeksforgeeks.org/b-tree-set-3delete/
https://medium.com/@vijinimallawaarachchi/all-you-need-to-know-about-deleting-keys-from-b-trees-9090f3334b5c