資料庫b樹

㈠ 資料庫索引為什麼使用B+樹

B tree： 二叉樹（Binary tree），每個節點只能存儲一個數。
B-tree： B樹（B-Tree，並不是B「減」樹，橫杠為連接符，容易被誤導）
B樹屬於多叉樹又名平衡多路查找樹。每個節點可以多個數（由磁碟大小決定）。
B+tree 和 B*tree 都是 B-tree的變種

一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁碟上。這樣的話，索引查找過程中就要產生磁碟I/O消耗，相對於內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁碟I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁碟I/O的存取次數。而B-/+/*Tree，經過改進可以有效的利用系統對磁碟的塊讀取特性，在讀取相同磁碟塊的同時，盡可能多的載入索引數據，來提高索引命中效率，從而達到減少磁碟IO的讀取次數。

不了解磁碟相關知識的可以查看 硬碟基本知識（磁頭、磁軌、扇區、柱面）

下面通過示意圖來看一下，B-tree、B+tree、B*tree

從圖中可以看出，B-tree 利用了磁碟塊的特性進行構建的樹。每個磁碟塊一個節點，每個節點包含了很關鍵字。把樹的節點關鍵字增多後樹的層級比原來的二叉樹少了，減少數據查找的次數和復雜度。

B-tree巧妙利用了磁碟預讀原理，將一個節點的大小設為等於一個頁（每頁為4K），這樣每個節點只需要一次I/O就可以完全載入。
B-tree 的數據可以存在任何節點中。

B+tree 是 B-tree 的變種，數據只能存儲在葉子節點。

B+tree 是 B-tree 的變種，B+tree 數據只存儲在葉子節點中。這樣在B樹的基礎上每個節點存儲的關鍵字數更多，樹的層級更少所以查詢數據更快，所有指關鍵字指針都存在葉子節點，所以每次查找的次數都相同所以查詢速度更穩定;

B*tree 每個磁碟塊中又添加了對下一個磁碟塊的引用。這樣可以在當前磁碟塊滿時，不用擴容直接存儲到下一個臨近磁碟塊中。當兩個鄰近的磁碟塊都滿時，這兩個磁碟塊各分出1/3的數據重新分配一個磁碟塊，這樣這三個磁碟塊的數據都為2/3。

在B+樹的基礎上因其初始化的容量變大，使得節點空間使用率更高，而又存有兄弟節點的指針，可以向兄弟節點轉移關鍵字的特性使得B*樹額分解次數變得更少；

㈡ 資料庫結構與演算法 在B樹中,每個非子葉結點的關鍵碼個數都在什麼之間

對於m叉的B樹
每個節點最多有m-1個關鍵碼,除根結點外的所有非葉結點至少有［m/2］個關鍵碼
若根結點是非子葉結點,則,至少有1個關鍵碼

㈢ b+樹和b樹的區別是什麼

B+樹索引是B+樹在資料庫中的一種實現，是最常見也是資料庫中使用最為頻繁的一種索引。B+樹中的B代表平衡（balance），而不是二叉（binary）。

（1）非葉子節點只能允許最多兩個子節點存在。

（2）每一個非葉子節點數據分布規則為左邊的子節點小當前節點的值，右邊的子節點大於當前節點的值(這里值是基於自己的演算法規則而定的，比如hash值)。

(3)資料庫b樹擴展閱讀：

與普通樹不同，普通樹的節點個數至少為1，而二叉樹的節點個數可以為0；普通樹節點的最大分支度沒有限制。

而二叉樹節點的最大分支度為2；普通樹的節點無左、右次序之分，而二叉樹的節點有左、右次序之分。

㈣ 紅黑樹，b+樹分別用於什麼場景，為什麼

紅黑樹屬於「黑平衡」的二叉樹，雖然犧牲了一定的平衡性，但是add、remove操作要由優於AVL樹也就是說RB-Tree的「統計性能」更佳！Java中TreeSet，TreeMap的底層都是基於RedBlackTree紅黑樹的；

B+樹主要用在文件系統以及資料庫做索引。比如磁碟存儲、文件系統、MySQL資料庫

㈤ 資料庫b樹葉節點是存儲數據頁嗎

B+ 樹是一種樹數據結構，是一個n叉樹，每個節點通常有多個孩子，

一棵B+樹包含根節點、內部節點和葉子節點。根節點可能是一個葉子節點，

也可能是一個包含兩個或兩個以上孩子節點的節點。

B+ 樹通常用於資料庫和操作系統的文件系統中。

NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系統都在使用B+樹作為元數據索引。

B+ 樹的特點是能夠保持數據穩定有序，

其插入與修改擁有較穩定的對數時間復雜度。B+ 樹元素自底向上插入。

㈥ 舉例說明oracle資料庫中B樹索引的基本組織結構

B樹 即二叉搜索樹： 1.所有非葉子結點至多擁有兩個兒子（Left和Right）； 2.所有結點存儲一個關鍵字； 3.非葉子結點的左指針指向小於其關鍵字的子樹，右指針指向大於其關鍵字的子樹； 如： B樹的搜索，從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那麼就命中；否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字； 如果B樹的所有非葉子結點的左右子樹的結點數目均保持差不多（平衡），那麼B樹的搜索性能逼近二分查找；但它比連續內存空間的二分查找的優點是，改變B樹結構（插入與刪除結點）不需要移動大段的內存數據，甚至通常是常數開銷； 如： 但B樹在經過多次插入與刪除後，有可能導致不同的結構： 右邊也是一個B樹，但它的搜索性能已經是線性的了；同樣的關鍵字集合有可能導致不同的樹結構索引；所以，使用B樹還要考慮盡可能讓B樹保持左圖的結構，和避免右圖的結構，也就是所謂的「平衡」問題； 實際使用的B樹都是在原B樹的基礎上加上平衡演算法，即「平衡二叉樹」；如何保持B樹結點分布均勻的平衡演算法是平衡二叉樹的關鍵；平衡演算法是一種在B樹中插入和刪除結點的策略； B-樹 是一種多路搜索樹（並不是二叉的）： 1.定義任意非葉子結點最多隻有M個兒子；且M>2； 2.根結點的兒子數為[2, M]； 3.除根結點以外的非葉子結點的兒子數為[M/2, M]； 4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字） 5.非葉子結點的關鍵字個數=指向兒子的指針個數-1； 6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]； 7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小於K[1]的子樹，P[M]指向關鍵字大於K[M-1]的子樹，其它P[i]指向關鍵字屬於(K[i-1], K[i])的子樹； 8.所有葉子結點位於同一層； 如：（M=3） B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為空，或已經是葉子結點；B-樹的特性： 1.關鍵字集合分布在整顆樹中； 2.任何一個關鍵字出現且只出現在一個結點中； 3.搜索有可能在非葉子結點結束； 4.其搜索性能等價於在關鍵字全集內做一次二分查找； 5.自動層次控制； 由於限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少利用率，其最底搜索性能為： 其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數； 所以B-樹的性能總是等價於二分查找（與M值無關），也就沒有B樹平衡的問題； 由於M/2的限制，在插入結點時，如果結點已滿，需要將結點分裂為兩個各佔M/2的結點；刪除結點時，需將兩個不足M/2的兄弟結點合並； B+樹 B+樹是B-樹的變體，也是一種多路搜索樹： 1.其定義基本與B-樹同，除了： 2.非葉子結點的子樹指針與關鍵字個數相同； 3.非葉子結點的子樹指針P[i]，指向關鍵字值屬於[K[i], K[i+1])的子樹（B-樹是開區間）； 5.為所有葉子結點增加一個鏈指針； 6.所有關鍵字都在葉子結點出現； 如：（M=3） B+的搜索與B-樹也基本相同，區別是B+樹只有達到葉子結點才命中（B-樹可以在非葉子結點命中），其性能也等價於在關鍵字全集做一次二分查找； B+的特性： 1.所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的； 2.不可能在非葉子結點命中； 3.非葉子結點相當於是葉子結點的索引（稀疏索引），葉子結點相當於是存儲（關鍵字）數據的數據層； 4.更適合文件索引系統； B*樹 是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針； B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）； B+樹的分裂：當一個結點滿時，分配一個新的結點，並將原結點中1/2的數據復制到新結點，最後在父結點中增加新結點的指針；B+樹的分裂隻影響原結點和父結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針； B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那麼將一部分數據移到兄弟結點中，再在原結點插入關鍵字，最後修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，並各復制1/3的數據到新結點，最後在父結點增加新結點的指針； 所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高； 小結 B樹：二叉樹，每個結點只存儲一個關鍵字，等於則命中，小於走左結點，大於走右結點； B-樹：多路搜索樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字范圍的子結點； 所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中； B+樹：在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中； B*樹：在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率從1/2提高到2/3 見：http://wenku..com/view/efd562d5b9f3f90f76c61bd0.html

㈦ HASH與B樹的聯系與區別

沒啥聯系。
b樹，一種結構，用以存放數據等等。
hash，演算法，包括很多種具體的演算法（數學邏輯），
db根據hash算出來的值控制數據存放的結構。

㈧ 高度為5的3階b樹至少有多少個關鍵字

31個關鍵字。

高度為5的三階B樹至少有31個結點。B樹即平衡查找樹，一般理解為平衡多路查找樹，也稱為B-樹、B_樹。是一種自平衡樹狀數據結構，能對存儲的數據進行O(log n)的時間復雜度進行查找、插入和刪除。B樹一般較多用在存儲系統上，比如資料庫或文件系統。

特點說明

B樹可以定義一個m值作為預定范圍，即m路（階）B樹。

每個節點最多有m個孩子。

每個節點至少有ceil(m/2)個孩子，除了根節點和葉子節點外。

對於根節點，子樹個數范圍為［2,m]，節點內值的個數范圍為［1,m-1]。

對於非根節點，節點內的值個數范圍為［ceil(m/2)-1,m-1]。

根節點（非葉子節點）至少有兩個孩子。

一個有k個孩子的非葉子節點包含k-1個值。

所有葉子節點在同一層。

節點內的值按照從小到大排列。

父節點的若干值作為分離值分成多個子樹，左子樹小於對應分離值，對應分離值小於右子樹。