msyql 为什么要使用B+树

为什么呢
为什么不使用二叉树、平衡树、红黑树、或者B树
首先确认一点
二叉树、平衡树、红黑树、尤其是红黑树
B树
他们的搜索速度的确够快
但是运用至计算机,其速度需要受到I/O制约
所以二叉树、平衡树、红黑树的深度太深,io次数太多,浪费性能
B树是因为数据和节点保存在一起,相同数量的数据,其深度会比较大
- 为什么会比较大?
先说明一种情况
正常是cpu和内存进行交互,内存和磁盘进行交互
磁盘读取是按页的,正常是4k或者8k
节点和数据同时保存,每页保存的数量肯定会变少,为了保存更大数据量的数据,树的深度肯定会加深
使用B+树
B+ 树除了页子节点,所有非页子节点都不保存数据,所以每页数据可以保存非常多的数量,间接导致同深度的树能保存更多的数据
引申出的问题
分表
- 水平分表
很容易理解,降低深度和减少数据量,就是为了降低io次数 - 垂直分表
原理是将大字段的io效率低,那就拆分出去,本表做查询然后做关联查询
为啥能提高速度
- 每次查询,内存很小,可以缓存,若是使用的都是短查询的话,缓存全命中,速度极大替快
- 数据量小了,查询肯定快
- 内存和存储是以页进行查找和定位的,单叶内数据越多,肯定io效率越好,速度越快