B+树 与 B树 索引
所属分类 mysql
浏览量 1628
B+树中只有叶子节点带有数据信息(直接保存数据或指向数据的指针),B树所有节点都带有数据信息
B+树索引分为聚集索引和非聚集索引
mysql使用B+树,Myisam是非聚集索引,innoDB是聚集索引
聚簇索引索引的叶节点就是数据节点 ,非聚簇索引的叶节点仍然是索引节点,只不过有一个指针指向对应的数据块。
B+树特点
所有关键字都出现在叶子结点(稠密索引),关键字有序
不可能在非叶子结点命中
非叶子结点是叶子结点的索引(稀疏索引),叶子结点存储(关键字)数据
B树与B+树区别
结构上
B+树中只有叶子节点会带有指向记录的指针,而B树则所有节点都带有,在内部节点出现的索引项不会再出现在叶子节点中。
B+树中所有叶子节点通过指针连接在一起,而B树不会。
性能上
B树只适合随机检索,B+树同时支持随机检索和顺序检索
B+树的磁盘读写代价更低。B+树的内部结点并没有指向关键字具体信息的指针,其内部结点比B树小,一次性读入内存中可以查找的关键字更多, IO读写次数是影响索引检索效率的最大因素。
B+树的查询效率更加稳定。B树搜索有可能会在非叶子结点结束,越靠近根节点的记录查找时间越短,只要找到关键字即可确定记录的存在,其性能等价于在关键字全集内做一次二分查找。而在B+树中,顺序检索比较明显,随机检索时,任何关键字的查找都必须走一条从根节点到叶节点的路,所有关键字的查找路径长度相同,导致每一个关键字的查询效率相当。
数据库索引采用B+树的主要原因
B树不支持顺序检索 遍历效率低
B+树的叶子节点使用指针顺序连接在一起,遍历叶子节点就可以实现整棵树的遍历。
数据库中基于范围的查询很多
B+树的内部结点没有指向关键字的指针,结构更小,更少的IO读写次数,更好的检索效率
相同大小的内存,可以载入更多的索引,提升检索效率
上一篇
下一篇
redis集群方案
Mysql innodb 为何建议使用自增列作为主键
redis使用zset保留最近的数据
B树与红黑树,为什么数据库使用B树索引
联合索引与最左匹配原则
Jedis客户端分片机制