從今天開始不講 Leetcode 了除非有想到什麼還沒點到。
後面要提一下對於其他知識點的準備，
畢竟如果什麼專案都沒有的話，
還是要有一些基礎知識可以唬爛（雖然我口才很差、要唬爛的時候又常常失憶..

先貼上我的 B B+ tree 心得，

因為發現很多後端會問，
所以我特別去了解這塊，
結果根本沒用上 XD

但如果能從 硬碟儲存（知道磁軌、硬碟是一次讀一個 block）了解到 indexing 的重要，
並且知道這些存在記憶體中的資料結構的怎麼設計而提升查找、IO 速度，
我覺得是很過癮的一件事。
不知道是學校太爛沒教還是普遍不會教，但了解這些不會吃虧的～

B Tree

每個 node 都有存 data 位置
Balanced Tree

• 檔案系統、DBMS 實現 multi-indexing 的資料結構，能有效率（較少 IO 次數）找到硬碟資料。
• 一種 [[M-way Search Tree]]，但對於 insert node 時有所有規定，所以平衡、不會歪斜。見下

Node insertion guideline

1. 能裝滿先裝滿
2. 每個 node 至少有 ceil(N / 2) 個 child
3. root 至少 2 個 child
4. leafs 都在同一 level（不代表是 full，只代表 1. 提到的，因為只要一個 node 有至少一個 child 就不會是 leaf）
5. bottom up（空間不夠，往 root 長）

在一個 node 擠爆時，取其中間（ceil or floor）拿上去當上層 index，然後 < 此中間值的放在左node，> 此中間值的放在右 node，保持 ceil(N/2) 個 child。

B+ Tree

只有 leaf nodes 存 data 位置，並且是一個 linked list。

• [[B Tree]] 的進化
• insert node 時有特定規則 [[B Tree#Node insertion guideline | (參考 B Tree)]]，所以平衡、不會歪斜
• 與 B Tree 相比，non leaf nodes 不存 data 位置，因此單次 IO 的資訊量較高

與 B Tree 相比:

1. 只有 leaf node 存有 data 位置。
2. leaf nodes 變成 linked list

這樣的好處是，查詢時，一個 node(block) 中 index 的範圍更大，進而減少 IO