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