理解進階資料結構（一）：B樹 ｜B+樹
樹是資料結構中很重要概念，不過當樹的枝葉越長越不平均，就像大樹歪向一側一樣，查找資料也會變得麻煩又費時。資料結構中的樹若失去平衡，查找效率會大大降低，甚至可能拖慢整個系統的速度。因此，我們需要設計能自我調整、保持平衡的樹，確保不管資料如何新增，都能快速查找。
以下內容為學習要點，但我建議學習樹看動畫會更容易理解。
此學習筆記若內容有誤，歡迎留言指正！
複習：二元搜尋樹 BST
我之前都記成BTS XD
一個節點只能存一個資料。左邊是最小，右邊最大。
一個節點存多筆資料效率高
如何存放資料？才能更有效率地找到資料？
如果數據量大到，葉子跟根的距離很遠，查找就會變得很沒效率。所以在資料結構裡，出現能夠讓一個節點同時存放多筆資料的設計，等於給我們的搜尋速度開了「加速模式」！尤其是當數據量龐大到無法一眼看完時，這些樹的特性就像是一條捷徑，讓我們更快找到答案。
M way search tree
每個節點最多可以有 M 位子節點(Children)，而每個節點可以放M-1個數值(key)。以下圖來說，這是 5 way search key。最多可以連五條線，即最多可以有個子節點。
https://faculty.cs.niu.edu/~freedman/340/340notes/340multi.htm
B 樹
- 特性：B 樹是一種多元樹（非二元），根節點最少有兩個子節點。每個節點可以存多個值，因而減少資料的偏斜。每個節點都是資料。
- 操作：插入或刪除時，節點會重新分配，且節點中的資料可能會“借”相鄰節點，來維持平衡。每次都會往上長。插入新資料，先拆分，再往上長
- 限制與規則：每個節點中的資料數量有上下限，通常為一個範圍值
m；節點裡的資料必須排序，讓搜尋和插入保持有序。刪除時，若節點內的資料少於最小值，會從相鄰節點「借資料」來保持平衡。 - 應用：資料庫索引，B 樹是搜尋大量資料（如交易匹配、資料庫檢索）的常見結構，因為每次操作會讓整個樹保持平衡。
- 參考動畫影片：Understanding B-Trees: The Data Structure Behind Modern Databases
B+ 樹：
跟 B 樹不一樣的是，他的資料僅存在最底層的 Leaf，其餘往上長的都是指標，指向最底層的實際資料值 ，而不用進行 Tree Travesal（遍歷）。
- 特性：擴充了 B 樹，除了根節點，每個節點都會有指標（leaf pointers），能直接找到下一個節點，無需重頭搜尋。最底層的葉節點是鏈結串列（Linked List）
- 操作：用指標定位到葉節點，大量資料的搜索效率更高。
- 應用：資料庫系統，如銀行交易，因為需要快速度查找和更新大量資料。
圖片來源：geeksforgeeks
B 樹與 B+樹兩者比較表格
AVL, 紅黑樹會在下個章節補充。
補充資料：
10.2 B Trees and B+ Trees. How they are useful in Databases
3會員
17內容數
留言0
查看全部
你可能也想看
Google News 追蹤
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
在知識爆炸的時代，有效地吸收與應用閱讀中的信息對學習者來說是一大挑戰。本文探討了三種不同層次的讀書筆記方法，包括局部碎片化的九合一讀書筆記、全局概覽的心智圖筆記及結構內化的閱讀心得文章。這些方法不僅有助於記錄和整理信息，還能促進理解與記憶，幫助學習者將知識內化為智慧，提升學習效果和實用能力。
這篇整理了我這個月讀到一些不在我分類中但很不錯內容，我也都有附上來源，如果你想了解我這個月發現了什麼不錯的內容都可以在這裡找到，而且我還會加上我的一點個人回饋
另外每月資訊量不同，造成每一類的內容不一，有的內容會比較多，如果你只想看精選，我會在每一類中都挑出 3 篇我最推的，前面會有星號
在現代學術研究中，閱讀大量文獻是一個必要且繁重的任務。然而，通過將學術閱讀流程標準化，能顯著提升效率，使閱讀變得更加有條理。最近，我實踐了兩個已經標準化的動作，每個動作都進行了50次以上的測試，效果顯著。
▋動作一：將文獻內容轉為資訊塊
這個動作的目的是將閱讀材料中的重要內容轉換為小而具
第1層(Rootfile)：原稿，生活紀錄資料，連結集錦，書單。
第2層：對第1層的內容做分類。例如將「原稿」進一步分成「書籍」「連載」「其他」。
第3層：對第2層的內容做個體化。例如將「書籍」進一步具體為書的名字。
第4層：對第3層的內容做結構化。
第5層：對第4層的內容做細節化。
本文介紹如何結合使用 Readwise 和 Readwise Reader 進行高效的碎片化閱讀與筆記管理。透過 Readwise Reader 閱讀多平台內容並進行高亮和筆記，利用 Readwise 整理和回顧劃線，並匯出至 Heptabase 和 Obsidian，提升學習效率，避免碎片化思考。
在現今這個資訊爆炸的時代，如何有效地管理和記錄知識成為許多人關心的問題。許多書籍和專家推薦各種最新的工具和方法，讓我們不禁覺得只要掌握了某種技術，就能輕鬆應對信息洪流。然而，真相往往並不如此簡單。持續不斷才是長期有效的關鍵。
在傳統的筆記方法中存在著分類僵化和過度依賴關鍵字的問題。卡片筆記以一張卡片一個知識，確保知識的獨立性，並且建立知識間的多重連接，形成網狀結構。 這本書介紹了用卡片筆記做知識管理的技巧，幫助大家將零散的知識系統化，從而在需要時能夠迅速提取並應用。
在學術寫作中，掌握「關鍵字閱讀」技術至關重要。
對於學術研究者來說，
有效地從大量的學術文獻中提煉出核心資訊是一項挑戰。
關鍵字閱讀不僅可以幫助你避免被不必要的細節所淹沒，
還能讓你更聚焦於與研究主題相關的資訊。
結合「書目卡 Bibcard」的使用，
這種閱讀方式能夠大大提高你的閱讀效
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
在知識爆炸的時代，有效地吸收與應用閱讀中的信息對學習者來說是一大挑戰。本文探討了三種不同層次的讀書筆記方法，包括局部碎片化的九合一讀書筆記、全局概覽的心智圖筆記及結構內化的閱讀心得文章。這些方法不僅有助於記錄和整理信息，還能促進理解與記憶，幫助學習者將知識內化為智慧，提升學習效果和實用能力。
這篇整理了我這個月讀到一些不在我分類中但很不錯內容，我也都有附上來源，如果你想了解我這個月發現了什麼不錯的內容都可以在這裡找到，而且我還會加上我的一點個人回饋
另外每月資訊量不同，造成每一類的內容不一，有的內容會比較多，如果你只想看精選，我會在每一類中都挑出 3 篇我最推的，前面會有星號
在現代學術研究中，閱讀大量文獻是一個必要且繁重的任務。然而，通過將學術閱讀流程標準化，能顯著提升效率，使閱讀變得更加有條理。最近，我實踐了兩個已經標準化的動作，每個動作都進行了50次以上的測試，效果顯著。
▋動作一：將文獻內容轉為資訊塊
這個動作的目的是將閱讀材料中的重要內容轉換為小而具
第1層(Rootfile)：原稿，生活紀錄資料，連結集錦，書單。
第2層：對第1層的內容做分類。例如將「原稿」進一步分成「書籍」「連載」「其他」。
第3層：對第2層的內容做個體化。例如將「書籍」進一步具體為書的名字。
第4層：對第3層的內容做結構化。
第5層：對第4層的內容做細節化。
本文介紹如何結合使用 Readwise 和 Readwise Reader 進行高效的碎片化閱讀與筆記管理。透過 Readwise Reader 閱讀多平台內容並進行高亮和筆記，利用 Readwise 整理和回顧劃線，並匯出至 Heptabase 和 Obsidian，提升學習效率，避免碎片化思考。
在現今這個資訊爆炸的時代，如何有效地管理和記錄知識成為許多人關心的問題。許多書籍和專家推薦各種最新的工具和方法，讓我們不禁覺得只要掌握了某種技術，就能輕鬆應對信息洪流。然而，真相往往並不如此簡單。持續不斷才是長期有效的關鍵。
在傳統的筆記方法中存在著分類僵化和過度依賴關鍵字的問題。卡片筆記以一張卡片一個知識，確保知識的獨立性，並且建立知識間的多重連接，形成網狀結構。 這本書介紹了用卡片筆記做知識管理的技巧，幫助大家將零散的知識系統化，從而在需要時能夠迅速提取並應用。
在學術寫作中，掌握「關鍵字閱讀」技術至關重要。
對於學術研究者來說，
有效地從大量的學術文獻中提煉出核心資訊是一項挑戰。
關鍵字閱讀不僅可以幫助你避免被不必要的細節所淹沒，
還能讓你更聚焦於與研究主題相關的資訊。
結合「書目卡 Bibcard」的使用，
這種閱讀方式能夠大大提高你的閱讀效