百度百科:
> B-tree(多路搜索樹,并不是二叉的)是一種常見的數據結構。使用B-tree結構可以顯著減少定位記錄時所經歷的中間過程,從而加快[存取速度]。按照翻譯,B 通常認為是Balance的簡稱。這個數據結構一般用于數據庫的索引,綜合效率較高。
> B-tree中,每個結點包含:
* 1、本結點所含關鍵字的個數;
* 2、指向父結點的指針;
* 3、關鍵字;
* 4、指向子結點的指針;
對于一棵m階B-tree,每個結點至多可以擁有m個子結點。各結點的關鍵字和可以擁有的子結點數都有限制,規定m階B-tree中,根結點至少有2個子結點,除非根結點為葉子節點,相應的,根結點中關鍵字的個數為1~m-1;非根結點至少有[m/2]([],向上取整)個子結點,相應的,關鍵字個數為[m/2]-1~m-1。
## 性能
B-tree有以下特性:
* 1、關鍵字集合分布在整棵樹中;
* 2、任何一個關鍵字出現且只出現在一個結點中;
* 3、搜索有可能在非葉子結點結束;
* 4、其搜索性能等價于在關鍵字全集內做一次二分查找;
* 5、自動層次控制;
由于限制了除根結點以外的非葉子結點,至少含有M/2個兒子,確保了結點的至少利用率,其最低搜索性能為:
其中,M為設定的非葉子結點最多子樹個數,N為關鍵字總數; 所以B-樹的性能總是等價于二分查找(與M值無關),也就沒有B樹平衡的問題; 由于M/2的限制,在插入結點時,如果結點已滿,需要將結點分裂為兩個各占M/2的結點;刪除結點時,需將兩個不足M/2的兄弟結點合并。
## 用途
鑒于B-tree具有良好的定位特性,其常被用于對檢索時間要求苛刻的場合,例如:
* 1、B-tree索引是數據庫中存取和查找文件(稱為記錄或鍵值)的一種方法。
* 2、硬盤中的結點也是B-tree結構的。與內存相比,硬盤必須花成倍的時間來存取一個數據元素,這是因為硬盤的機械部件讀寫數據的速度遠遠趕不上純電子媒體的內存。與一個結點兩個分支的二元樹相比,B-tree利用多個分支(稱為子樹)的結點,減少獲取記錄時所經歷的結點數,從而達到節省存取時間的目的。
## B+樹
另外還有一種與此類似的樹結構叫B+樹,像 Berkerly DB , sqlite , mysql 數據庫都使用了B+樹算法處理索引。 B+和B-(即B)是因為每個結點上的關鍵字不同。一個多一個,一個少一個。 對于B+樹,其結點結構與B-tree相同,不同的是各結點的關鍵字和可以擁有的子結點數。如m階B+樹中,每個結點至多可以擁有m個子結點。非根結點至少有[m/2]個子結點,而關鍵字個數比B-tree多一個,為[m/2]~m。 這兩種處理索引的數據結構的不同之處:
* 1。B樹中同一鍵值不會出現多次,并且它有可能出現在葉結點,也有可能出現在非葉結點中。而B+樹的鍵一定會出現在葉結點中,并且有可能在非葉結點中也有可能重復出現,以維持B+樹的平衡。
* 2。因為B樹鍵位置不定,且在整個樹結構中只出現一次,雖然可以節省存儲空間,但使得在插入、刪除操作復雜度明顯增加。B+樹相比來說是一種較好的折中。
* 3。B樹的查詢效率與鍵在樹中的位置有關,最大時間復雜度與B+樹相同(在葉結點的時候),最小時間復雜度為1(在根結點的時候)。而B+樹的時間復雜度對某建成的樹是固定的。
- 說明
- 排序
- java實現
- 二分歸并排序
- 快速排序
- js實現
- 冒泡排序 (Bubble Sort)
- 快速排序-js
- ES6-rest參數
- 比較排序
- 堆排序
- 插入排序
- 歸并排序
- 選擇排序
- shellSort
- 排序基礎知識
- 其他
- Rabbit
- chickenProblem
- 漢諾塔
- 取出兩個字符串中開頭相同的部分
- 兩個七進制輸入,輸出七進制
- 二維數組(矩陣)對角線輸出
- 根據概率取值
- 最小編輯距離算法
- 列劃分算法
- 數組去重
- 數組去重1
- 在一天里,鐘表的時針和分針會重合多少次?
- 找第二大問題
- Raft算法
- B-tree
- Leetcode JAVA實現
- leetcode1. 2 Sum
- leetcode2. Add Two Numbers
- leetcode7. Reverse Integer
- leetcode8. String to Integer (atoi)
- leetcode12. Integer to Roman
- leetcode13. Roman to Integer
- leetcode15. 3Sum
- leetcode18. 4Sum
- leetcode20. Valid Parentheses
- leetcode26. Remove Duplicates from Sorted Array
- leetcode27. Remove Element
- leetcode58. Length of Last Word
- leetcode66. Plus One
- leetcode67. Add Binary
- leetcode80. Remove Duplicates from Sorted Array II
- leetcode 88. Merge Sorted Array
- leetcode101. Symmetric Tree
- leetcode104. Maximum Depth of Binary Tree
- leetcode110. Balanced Binary Tree
- leetcode118. Pascal's Triangle
- leetcode119. Pascal's Triangle II
- leetcode121. Best Time to Buy and Sell Stock
- leetcode125. Valid Palindrome
- leetcode136. Single Number
- leetcode144. Binary Tree Preorder Traversal
- leetcode145. Binary Tree Postorder Traversal
- leetcode155. Min Stack
- leetcode169. Majority Element
- leetcode171. Excel Sheet Column Number
- leetcode172. Factorial Trailing Zeroes
- leetcode189. Rotate Array
- leetcode191. Number of 1 Bits
- leetcode202. Happy Number
- leetcode203. Remove Linked List Elements
- leetcode204. Count Primes
- leetcode225. Implement Stack using Queues
- leetcode226. Invert Binary Tree
- leetcode231. Power of Two
- leetcode232. Implement Queue using Stacks
- leetcode234. Palindrome Linked List
- leetcode237. Delete Node in a Linked List
- leetcode242. Valid Anagram
- leetcode258. Add Digits
- leetcode263. Ugly Number
- leetcode283. Move Zeroes
- leetcode292. Nim Game
- leetcode344. Reverse String
- leetcode371. Sum of Two Integers
- leetcode804. Unique Morse Code Words
- Leetcode JS 實現
- Js-leetcode 1. Two Sum
- Js-leetcode 2. Add Two Numbers
- Js-leetcode 10. Regular Expression Matching
- Js-leetcode 14. Longest Common Prefix
- Js-leetcode 17.Letter Combinations of a Phone Number
- Js-leetcode 20. Valid Parentheses
- Js-leetcode 27. Remove Element
- Js-leetcode 30. Substring with Concatenation of All Words
- Js-leetcode 35. Search Insert Position
- Js-leetcode 41. First Missing Positive
- Js-leetcode 48. Rotate Image
- Js-leetcode 53. Maximum Subarray
- Js-leetcode 54. Spiral Matrix
- Js-leetcode 73. Set Matrix Zeroes
- Js-leetcode 75. Sort Colors
- Js-leetcode 85. Maximal Rectangle
- Js-leetcode 89. Gray Code
- Js-leetcode 93.Restore IP Addresses
- Js-leetcode 98. Validate Binary Search Tree
- Js-leetcode 104. Maximum Depth of Binary Tree
- Js-leetcode 118. Pascal's Triangle
- Js-leetcode 121. Best Time to Buy and Sell Stock
- Js-leetcode 136. Single Number
- Js-leetcode 164. Maximum Gap
- Js-leetcode 189. Rotate Array
- Js-leetcode 215. Kth Largest Element in an Array
- Js-leetcode 217. Contains Duplicate
- Js-leetcode 258. Add Digits
- Js-leetcode 263.Ugly Number
- Js-leetcode 283. Move Zeroes
- Js-leetcode 326. Power of Three
- Js-leetcode 434. Number of Segments in a String
- Js-leetcode 459. Repeated Substring Pattern
- Js-leetcode 507. Perfect Number
- Js-leetcode 537. Complex Number Multiplication
- Js-leetcode 541. Reverse String II
- Js-leetcode 551. Student Attendance Record I
- Js-leetcode 557. Reverse Words in a String III
- Js-leetcode 605. Can Place Flowers
- Js-leetcode 606. Construct String from Binary Tree
- Js-leetcode 621. Task Scheduler
- Js-leetcode 622. Design Circular Queue
- Js-leetcode 633. Sum of Square Numbers
- Js-leetcode 657. Robot Return to Origin
- Js-leetcode 682. Baseball Game
- Js-leetcode 686. Repeated String Match
- Js-leetcode 696. Count Binary Substrings
- Js-leetcode 709.To Lower Case.md
- Js-leetcode 771 Jewels and Stones
- Js-leetcode 804.Unique Morse Code Words
- Js-leetcode 867. Transpose Matrix
- Js-leetcode 905. Sort Array By Parity
- Js-leetcode 914. X of a Kind in a Deck of Cards
- Js-leetcode 922. Sort Array By Parity II
- Js-leetcode 1221. Split a String in Balanced Strings
- Js-leetcode 3. Longest substring without repeating characters
- document
- 劉宇波老師--基礎知識
- 算法與數據結構
- 數據機構與算法介紹
- 二叉樹
- 堆
- 鏈表
- 隊列
- 并查集
- 最小生成樹
- 圖論
- 最短路徑
- 總結
- 玩轉數據結構
- 介紹
- 數組
- 棧和隊列
- 玩轉鏈表
- 鏈表與遞歸
- 二分搜索樹
- 集合與映射
- 第8章 優先隊列和堆
- 第9章 線段樹
- 第10章 Trie
- 玩轉算法面試 leetcode題庫分門別類詳細解析
- 第一章 介紹
- 第二章 時間復雜度和空間復雜度
- 第三章
- 深度實戰玩轉算法
- JS數據結構與算法
- 第一章.介紹
- 第二章.字符串
- 第三章.數組
- 第四章
- 第五章.排序
- 第六章.遞歸
- 第七章.棧
- 第八章.隊列
- 第九章.鏈表
- 第十章.矩陣
- 第十一章.二叉樹
- 第十二章.堆
- 極客時間
- 第01課丨數據結構與算法總覽
- 第02課丨訓練準備和復雜度分析
- 第03課丨數組、鏈表、跳表
- 第04課丨棧、隊列、優先隊列、雙端隊列
- 算法基礎
- 哈希表(散列表)
- 異或運算
- leetcode
- KD樹(K-Dimension Tree)
- Rtree
- B站-左神
- 一周刷爆LeetCode,算法大神左神(左程云)耗時100天打造算法與數據結構基礎到高級全家桶教程,直擊BTAJ等一線大廠必問算法面試題真題詳解
- 簡單的排序算法
- 認識Nlog(N)的算法
- 第三節:桶排序及排序算法總結
- 左程云算法課程
- 1 認識復雜度、對數器、二分法與異或運算
- 2 鏈表結構、棧、隊列、遞歸行為、哈希表和有序表
- 10道BAT必問算法面試題
- 超級水王問題
- 78節
- 04鏈表