首页   快速返回

B树与红黑树,为什么数据库使用B树索引     所属分类 mysql
红黑树是每个节点都带有颜色属性的二叉查找树

B树是为了磁盘或其它存储设备而设计的一种平衡多路查找树,
相对于二叉,B树每个内节点有多个分支,
与红黑树相比,在相同的的节点的情况下,一颗B树的高度远远小于红黑树的高度

B树操作时间 = 磁盘读写时间 + CPU计算时间 , 
CPU速度非常快,B树的操作效率取决于磁盘读写时间,取决于磁盘读写次数,
关键字总数相同的情况下B树的高度越小,磁盘IO所花的时间越少.

二叉查找树的结构不适合数据库,查找效率与层数相关。
对于数据库来说,每进入一层,就要从硬盘读取一次数据,硬盘的读取时间远远大于数据处理时间,数据库读取硬盘的次数越少越好。
B树有利于减少硬盘读取的次数。
假定一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据,换成二叉查找树,需要20层!
假定操作系统一次读取一个节点,并且根节点保留在内存中,那么B树在100万个数据中查找目标值,只需要读两次硬盘。

 B+树 与 B树 索引  

上一篇     下一篇
Mysql innodb 为何建议使用自增列作为主键

redis使用zset保留最近的数据

B+树 与 B树 索引

联合索引与最左匹配原则

Jedis客户端分片机制

一致性hash与treemap