Ⅰ b樹與b+樹的區別是什麼
一、關鍵字不同
1、b樹每一個關鍵字有且只出現一次，且所有關鍵字按照從小到大的順序進行排列。
2、而b+樹有n棵子樹的非葉節點有n個關鍵字，關鍵字會存儲重復。非葉節點只保存關鍵字，僅包含子樹的最大或者最小的關鍵字，只用來索引，關鍵字從小到大排列。
二、存儲內容不同
1、b樹每個節點除了存儲關鍵字，還存儲數據。
2、b+樹所有葉子節點存儲內容包含全部的關鍵字信息，以及指向關鍵字記錄的指針。
三、查找不同
1、b樹查找相當於二分查找，可以在非葉節點結束，且若經常訪問的元素離根節點較近，則訪問更加迅速。
2、而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-樹的形式保存
你找本數據結構的書看看吧，B-樹一兩句說個定義對你也沒意義。
其他的存儲形式多了，鏈表，順序表，棧，隊列，二叉樹，紅黑樹，平衡二叉樹，優先隊列……還是那句話，找本數據結構的書看看
Ⅳ 數據結構中B樹、B+樹的區別
一、B樹的起源
B樹，最早是由德國計算機科學家Rudolf Bayer等人於1972年在論文 《Organization and Maintenance of Large Ordered Indexes》提出的，不過我去看了看原文，發現作者也沒有解釋為什麼就叫B-trees了，所以把B樹的B，簡單地解釋為Balanced或者Binary都不是特別嚴謹，也許作者就是取其名字Bayer的首字母命名的也說不定啊……
二、B樹長啥樣
還是直接看圖比較清楚，圖中所示，B樹事實上是一種平衡的多叉查找樹，也就是說最多可以開m個叉（m>=2），我們稱之為m階b樹，為了體現本博客的良心之處，不同於其他地方都能看到2階B樹，這里特意畫了一棵5階B樹 。
B+樹的查找過程，與B樹類似，只不過查找時，如果在非葉子節點上的關鍵字等於給定值，並不終止，而是繼續沿著指針直到葉子節點位置。因此在B+樹，不管查找成功與否，每次查找都是走了一條從根到葉子節點的路徑
Ⅳ 高度為5的3階b樹至少有多少個關鍵字
高度為5的3階b樹至少有31個關鍵字。
B樹和B+樹區別：
關鍵字數量不同，B+樹分支結點M個關鍵字，葉子節點也有M個，B樹分支結點則存在 k-1 個關鍵碼。
數據存儲位置不同，B+樹數據存儲在葉子結點上，B樹存儲在每個結點上。
查詢不同，B+樹是從根節點到葉子節點的路徑，B樹是只需要找到數據就可以。
分支節點存儲信息不同，B+樹存索引信息，B樹存的是數據關鍵字。
B樹，二叉樹，每個結點只存儲一個關鍵字，等於則命中，小於走左結點，大於走右結點。
B-樹，多路搜索樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字范圍的子結點，所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中。
B+樹，在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引，B+樹總是到葉子結點才命中。
B*樹，在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率從1/2提高到2/3。
Ⅵ 數據結構B樹
比如說一顆 B 樹的階為 1001（即 1 個節點包含 1000 個關鍵字），高度為 2，它可以儲存超過 10 億個關鍵字，我們只要讓根節點持久地保留在內存中，那麼在這棵樹上，尋找某一個關鍵字至多需要兩次硬碟的讀取即可。
Ⅶ 淺析B樹與硬碟數據存儲
1.什麼是B樹
非葉子節點不存儲data,只存儲索引(冗餘),可以放更多的索引
葉子節點包含所有索引欄位
葉子節點用雙向指針相連，提高區間訪問性
2.硬碟數據如何存儲以及讀寫
3.為什麼硬碟要引入B樹作為數據管理的方式
B樹的節點中還包含了一些關鍵字信息data，這個data也占據著一定的數據量，如果把data去掉，這樣就又能多加很多子節點了。這也就是B+樹的核心思想。
相關博客: https://blog.csdn.net/qq_24313635/article/details/102924190
Ⅷ 順序+折半+分塊查找+B樹和(B+)樹
（線性查找）
1.一般線性表的順序查找
引入哨兵，使得循環時不必判斷是否越界
ASL成功=(n+1)/2
ASL失敗=n+1
2.有序表的順序查找
查找判定樹
（二分查找）
僅適用於有序的順序表
判定樹
ASL成功=log2(n+1)-1
（索引順序查找）
吸取了順序查找和折半查找各自的優點，即有動態結構，又適於快速查找。
基本思想 ：將查找表分為若乾子塊，塊內無序，塊間有序。前一個塊中的最大關鍵字小於後一塊中所有記錄的關鍵字。建立一個索引表，索引表中的每個元素含有各塊的最大關鍵字和各塊中的第一個元素的地址，索引表按關鍵字有序排序。
（多路平衡查找樹）
一棵m階B樹或為空樹，或為滿足如下特性的m叉樹
1.樹中每個節點最多有m課子樹（m-1個關鍵字）
2.若根節點不是終端節點，則至少有兩棵子樹
3.除根節點外的所有非葉節點至少有⌈m/2⌉棵子樹（⌈m/2⌉-1個關鍵字）
4.非葉結點的結構為
n個關鍵字，n+1個指針
Ki為關鍵字且按順序排列
Pi為指向子樹的指針
Pi-1所指子樹的值均小於Ki，Pi所指子樹的指均大於Ki
n為結點中關鍵字的個數
5.所有葉節點都出現在同一層次上，且不帶信息，實際不存在指針為空
B樹的高度
磁碟的存取次數
（不包括最後的不帶信息葉結點那層）
B樹的查找
1.在B樹中找結點
2.在結點內找關鍵字
由於B樹常存儲在磁碟上，因此前一個查找操作是在磁碟上進行的，後一個是在內存中進行。
查找到某個節點後，先在有序表中進行查找，若找到則查找成功，否則按照對應的指針信息到所指的子樹中去查找，查找到葉結點時，則說明樹中沒有對應關鍵字，查找失敗。
B樹的插入
1.定位：利用B樹查找法，找出插入該關鍵字的最低層中的某個非葉節點
2.插入：插入後節點的關鍵字數小於m則可直接插入，否則對結點進行分裂
3.分裂：取一個新結點，在插入key後的原節點從中間位置將其中的關鍵字分為兩部分，左邊的部分留在原節點，右邊的部分去新結點，中間位置（m/2向上取整）的節點插入到父節點，若導致父節點個數大於m-1，則繼續分裂直至這個過程到根節點為止，此時會導致B樹高度增加1
pic
B樹的刪除
將被刪除關鍵字Ki與它的左或右子節點中最相近的關鍵字Ki'替代它，再遞歸刪除Ki'
有以下幾種情況
1.若其所在節點的關鍵字數大於⌈m/2⌉-1，則直接刪除
2.若其所在節點的關鍵字數等於⌈m/2⌉-1，兄弟節點關鍵字數大於⌈m/2⌉-1，父節點對應關鍵字加到所在節點中，兄弟節點中的一個關鍵字移到父節點
3.若其所在節點的關鍵字數等於⌈m/2⌉-1，左右兄弟節點關鍵字數也均等於⌈m/2⌉-1，就把父節點中對應的那個關鍵字加到所在子節點與其某個兄弟節點合並後的節點中
合並過程會導致父節點中關鍵字減少，若是根節點個數減少到0，則刪除根節點，將合並後的節點作為新的根。若非根節點減少到⌈m/2⌉-2，則又要與它自己的兄弟節點進行調整或合並操作。
圖解
https://www.jianshu.com/p/a858bb15cbf0
1.樹中每個節點最多有m課子樹
2.若根節點不是終端節點，則至少有兩棵子樹，除根節點外的所有非葉節點至少有⌈m/2⌉棵子樹
4.結點的子樹個數與關鍵字個數相同
5.所有葉結點包含全部關鍵字及指向相應記錄的指針，葉結點中將關鍵字按大小順序排列，並且相鄰葉結點按大小順序相互鏈接起來
6.所有分支節點中僅包含它的各個子節點中關鍵字的最大值
兩種查找方式
Ⅸ 數據結構中什麼是B樹
B 樹是為了磁碟或其它存儲設備而設計的一種多叉（下面你會看到，相對於二叉，B樹每個內結點有多個分支，即多叉）平衡查找樹。
B 樹又叫平衡多路查找樹。一棵m階的B 樹 (m叉樹)的特性如下：樹中每個結點最多含有m個孩子（m>=2）；除根結點和葉子結點外，其它每個結點至少有[ceil(m / 2)]個孩子（其中ceil(x)是一個取上限的函數）；若根結點不是葉子結點，則至少有2個孩子（特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有一個根節點）；所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息(可以看做是外部接點或查詢失敗的接點，實際上這些結點不存在，指向這些結點的指針都為null)；每個非終端結點中包含有n個關鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
a) Ki (i=1...n)為關鍵字，且關鍵字按順序升序排序K(i-1)< Ki。
b) Pi為指向子樹根的接點，且指針P(i-1)指向子樹種所有結點的關鍵字均小於Ki，但都大於K(i-1)。
c) 關鍵字的個數n必須滿足： [ceil(m / 2)-1]<= n <= m-1。
Ⅹ b樹和b+樹有什麼區別
B+樹是B樹的一種變體，也屬於平衡多路查找樹，大體結構與B樹相同，包含根節點、內部節點和葉子節點。
B樹的非葉子節點存有數據，而B+樹的非葉子節點沒有存有樹，b樹它是一種多路的平衡搜索樹，B+樹更適合外部存儲，B+樹中所有葉子節點都是通過指針連接在一起，而B樹不會。
b樹和b+樹之間的區別
B+樹是B樹的一種變體，也屬於平衡多路查找樹， B+樹中只有葉子節點會帶有指向記錄的指針ROWID，B+樹的優點，葉子節點之間通過指針來連接，范圍掃描將十分簡單，B+樹中所有葉子節點都是通過指針連接在一起。
B樹則所有節點都帶有，在內部節點出現的索引項不會再出現在葉子節點中。B樹的優點，對於在內部節點的數據，可直接得到，不必根據葉子節點來定位。B樹通常意味著所有的值都是按順序存儲的，並且每一個葉子到根的距離相同。
B是balance，平衡的意思，所以，B樹首先是一棵平衡樹，而平衡樹首先得是一棵排序數。所以B樹就是一棵平衡的、排序的多叉樹。