MySQL为什么要用B+树做索引,而不是其他的树?比如B树

简单回答

因为B树不管叶子节点还是非叶子节点都会保存数据,这样导致在非叶子节点中能保存的指针数量变少。而指针少的情况下要保存大量数据,只能增加树的高度,这样就导致IO操作变多,查询性能降低。

B+树是在在叶子节点存放数据,查找速度快除了树的层数不高外,叶子节点还维持了一个链表,查询时相当于顺序查找这个链表。更重要的是,查询时对磁盘的IO操作不仅仅查询了这个数据所在块的信息,也将这个块附近的块也加进来了,这样下次查询时,就不用再次IO,变相加快了查询速度。

拓展

在计算机中,磁盘存储数据的最小单元是扇区,一个扇区的大小是512字节,而文件系统的最小单元是块,一个块是4K,而对于InnDB存储引擎来说它的最小存储单元是页(page),一个页的大小是16K。

数据既然都存储在页中,那么如何查找数据就成了一个问题。因为不知道要查找的数据存在哪个页中,也不可能把所有的页都遍历一遍。

页既可以用来存放数据也可以用来存放键值和指针,在B+树中叶子节点存放数据,非叶子节点存放键值和指针。

索引组织表通过非叶子节点的二分查找以及指针确定数据在哪个页中,进而再去数据页中查找到需要的数据。

在InnoDB中B+树高度一般为1-3层,这就能满足千万级的数据存储。在查找数据时,一次页的查找代表一次IO,所以通过主键索引查询通常只需要1-3次IO操作即可查到数据。

参考资料
面试官:为什么 MySQL 索引要使用 B+树而不是其它树形结构?比如 B 树?

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容