B-树

由AVL引入B树。内存上都是O(logn)，主要是优化了磁盘IO。
拿2000W的数据来说事儿。AVL在最坏的情况下需要log(2000W)/log(2) = 25，25次磁盘I/O是一个很糟糕的速度；磁盘的读取是按块来的，把B树节点设置成块大小将对磁盘I/O非常友好，假设一个节点存500个，只需要log(2000W)/log(500) = 3次。

data里面存的东西可以是数据、指针（和存储引擎有关）

缺点

1. 搜索的快慢和离根节点的远近有关。花费的磁盘I/O次数不平均
2. 每个节点里面的key被data缩减了空间。
3. 不方便做范围搜索，整表遍历也看起来不方便

B+树

（磁块4多画了10）

每个非叶子节点，只存放key，不存放data。

1. 层数会更低，搜索效率会更好
2. 搜索的时间平均，data都在叶子
3. 叶子节点被串在链表中，形成了一个有序链表，在进行整表搜索时可以直接遍历叶子节点的有序链表。范围查询可以直接遍历叶子节点的有序链表。