部分参考:B树和B+树的区别
MySQL为什么使用树结构?
- 文件很大,不可能全部存储在内存中,故要存储到磁盘上
- 索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数(为什么使用B-/+Tree,还跟磁盘存取原理有关)
- 局部性原理与磁盘预读,预读的长度一般为页(page)的整倍数(操作系统内存页的大小通常为4k)。其中MySQL B+树中的 叶/非叶节点 都是以MySQL的页为单位(大小通常也为16k),存放完整行记录。
- 数据库系统巧妙利用了磁盘预读原理,将一个节点大小设为操作系统内存页的整数倍,这样每个节点只需要一次I/O就可以完全载入。而红黑树这种结构,高度明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性。
参考:磁盘读取
计算机系统是分页读取和存储的,一般一页为4KB(8个扇区,每个扇区512B,8*512B=4KB),每次读取和存取的最小单元为一页,而磁盘预读时通常会读取页的整倍数。
根据文章上述的【局部性原理】①当一个数据被用到时,其附近的数据也通常会马上被使用。②程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),所以即使只需要读取一个字节,磁盘也会读取一页的数据。
MySQL InnoDB默认的页大小为16k(可通常 innodb_page_size 参数设置),而操作系统中的磁盘页大小通常为4k,所以这里可以认为MySQL InnoDB中的1页(1个磁盘块)相当于操作系统中的4页。
这也就符合MySQL InnoDB所利用到的磁盘预读通常会预读操作系统页的整数倍(4倍)。具体如下图:
编辑
最外层浅蓝色磁盘块1里有数据17、35(深蓝色)和指针P1、P2、P3(黄色)。P1指针表示小于17的磁盘块,P2是在17-35之间,P3指向大于35的磁盘块。真实数据存在于叶子节点也就是最底下的一层3、5、9、10、13......非叶子节点不存储真实的数据,只存储指引搜索方向的数据项,如17、35。
查找过程:例如搜索28数据项,首先加载磁盘块1到内存中,发生一次I/O,用二分查找确定在P2指针。接着发现28在26和30之间,通过P2指针的地址加载磁盘块3到内存,发生第二次I/O。用同样的方式找到磁盘块8,发生第三次I/O。
真实的情况是,上面3层的B+Tree可以表示2k万的数据,这种量级的数据只发生了三次I/O,时间提升是巨大的。
B树和B+树的区别:
- B树的每个节点都存储了key和data,而B+树的data存储在叶子节点上。
B+树非叶子节点仅存储key不存储data,这样一个节点就可以存储更多的key。可以使得B+树相对B树来说更矮(IO次数就是树的高度),所以与磁盘交换的IO操作次数更少。 - B+树所有叶子节点构成一个有序链表,按主键排序来遍历全部记录,能更好支持范围查找。
由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历,相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。 - B+树所有的查询都要从根节点查找到叶子节点,查询性能更稳定;而B树,每个节点都可能查找到数据,需要在叶子节点和内部节点不停的往返移动,所以不稳定。