从今天开始不讲 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