有序的数据结构中:内存操作红黑树快,磁盘操作b+树快

时间:2023-01-12 14:12:50

红黑树常用于存储内存中的有序数据,增删很快,b+树常用于文件系统和数据库索引,因为b树的子节点大于红黑树,红黑树只能有2个子节点,b树子节点大于2,子节点树多这一特点保证了存储相同大小的数据,树的高度更小,数据局部更加紧凑,而硬盘读取有局部加载的优化(把要读取数据和周围的数据一起预先读取),b树相邻数据物理上更加紧凑这一特点符合硬盘进行io优化的特性。b+树在b树基础上进一步将数据只存在叶子节点,非叶子节点不存值只存储值的指向,这使得单个节点能有更多子节点,除此之外将所有叶子节点(值存在叶子节点)放入链表中,使得数据更加紧凑有序,只需要链表(叶子节点)的一次遍历就能获取所有树上的值。b+树这些特性适合用于数据库的索引,mysql底层数据结构就是b+树。

  个人总结,若有不当恳请不吝赐教。

参考博文:

b树b+树23树,mysql索引
https://www.cnblogs.com/vincently/p/4526560.html