高性能设计与数据库各种树结构

1. B+树：传统关系型数据库广泛采用B+树，B+树是对数据排好序后再存储，加快数据检索速度。
   
   目前大多数DB多采用两级索引的B+树，树的层次最多三层。因此可能需要5次磁盘访问才能更新一条记录（三次磁盘访问获得数据索引及行ID，一次数据文件读操作，一次数据文件写操作，终于知道数据库操作有多麻烦多耗时了）
2. LSM树：NoSQL（例如：HBase）产品广泛采用LSM树。
   
   具体思想是：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘。不过读取的时候稍微麻烦，需要合并磁盘中历史数据和内存中最近的修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。
   
   LSM树的原理是：把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会被清除并写入到磁盘中，磁盘中的树定期可以做合并操作，合并成一棵大树，以优化读性能。

参考：

平衡二叉树、B树、B+树、B*树

【面试现场】为什么MySQL数据库要用B+树存储索引？

性能测试与高性能架构

大型网站技术架构：核心原理与案例分析