data structure in DB
B树
B+树
B树和B+树的区别
- B树节点无重复元素
- B树的中间节点会存储数据指针,B+树只有叶子节点存储
- B+树的叶子串联在一起,有指针指向下一个节点,可以顺序扫描,必须在叶子上找到数据,查找时间稳定为O(logN)
- B+树更矮胖
并发策略:加读写锁
SkipList
- Redis底层结构
LSM树
- Log Structured Merge Tree,利用磁盘顺序写性能好于随机写特性,将批量随机写转换为一次性顺序写
- 两个以上存储结构组成。C0 tree(MemTable)在内存,如红黑树、map;C1 tree(SSTable)在硬盘,如B树
- 应用
哈希表
数据库类型
- 关系型数据库(SQL): MySQL、PostgreSQL、Oracle
- k-v型(NoSQL):Redis、MongoDB
数据组织
以页存储
Heap file和 Index Organized Table组织页面
扩展方式
- share-storage:一写多读,共享底层存储,仅支持单点写入;兼容开源数据库
- share-nothing
- 不共享存储,自己管理分区,多用于分布式数据库,如BigTable、Spanner、TiDB、OceanBase
- 采用LSM树,上层采用Paxos、Raft等共识算法
cover
id:103202182
画师:balabling
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 suisbuds!