略微加速

略速 - 互联网笔记

为什么MySQL数据库要用B+树存储索引

2020-12-01 leiting (2281阅读)

标签 MySql

文件系统和数据库的索引都是存在硬盘上的,并且如果数据量大的话,不一定能一次性加载到内存中。


数据库中 Select 数据,不一定只选一条,很多时候会选多条,比如按照 ID 排序后选 10 条。


如果是多条的话,B 树需要做局部的中序遍历,可能要跨层访问。


而 B+ 树由于所有数据都在叶子结点,不用跨层,同时由于有链表结构,只需要找到首尾,通过链表就能把所有数据取出来了。


如果只选一个数据,那确实是 Hash 更快。但是数据库中经常会选择多条,这时候由于 B+ 树索引有序,并且又有链表相连,它的查询效率比 Hash 就快很多了。


而且数据库中的索引一般是在磁盘上,数据量大的情况可能无法一次装入内存,B+ 树的设计可以允许数据分批加载,同时树的高度较低,提高查找效率。


http://stor.51cto.com/art/201903/593329.htm


北京半月雨文化科技有限公司.版权所有 京ICP备12026184号-3