前言
很久以前有学习过各种树结构, 但后来真的没有在实际项目中运用到. 毕竟我主要负责的都是写业务代码. 太上层了
但是忘光光还是很可惜的. 所以久久可以复习一下. 记得概念也好, 帮助思考.
参考:
mysql底层原理-二叉树、红黑树、BTree、B+Tree
二叉树
规则是左边要比右边小. 它最大的问题就是会很深, 像上面这样. 每多一层就 IO 读写多一次, 就慢 (因为读 IO 是物理操作, 要移动磁头, 这个和读 ram 通通电, 不同级别). 所以它不可以用来做 database 数据结构.
红黑树
红黑是二叉的查询优化, 所有查询优化都是建立在提前对数据结构处理的. 所以 insert, update, delete 一定会变慢.
红黑树多了一些规则, 确保树没有那么深 (做了一些平衡), 每当新节点插入的时候, 树结构就有可能因为要满足条件而调整.
B 树
B 树有对红黑进行了优化, 利用了磁盘每一次读取最少 16k 的原理, 它把每个节点都大一些, 那么上面一个圆圈就不只一个数目.
和红黑的目的一样就是想办法让树不要那么深, 减少磁盘读取.
B+ 树
对 B 树做了优化, data size 太大, 会导致磁盘块太大, 所以把 data 都移到了最底部.
结论
数据库的设计和找字典是一样概念, 上面这些磁盘块, 就好比字典的目录,
比如我找 Derrick 这个字, 一页一页翻肯定很慢, 但是有一个 A-Z 的目录, 里面就 26 个字母.
先把目录读出来, 然后 loop 到 D, 那么就锁定 D 的范围了. 过滤了大部分不相关的字.
所谓的 index 就是目录. 依据不同 column 排序.
p.s 红黑, B 树 抽象都是平衡二叉树, 目的都为了平衡, B-树就是B树来的. 只是因为有一个B+树所以就把原来的叫B-树.