B+树
- 简介：为了改善数据访问特性，文件系统或数据库系统通常会对数据排序后存储，加快数据检索速度。传统关系数据库的做法是使用B+树，保证数据在不断更新、插入、删除后依然有序。B+树结构如下图所示。
- B+树是一种专门针对磁盘存储而优化的N叉排序树，以树节点为单位存储在磁盘中，从根开始查找所需数据所在的节点编号和磁盘位置，将其加载到内存中然后继续查找，直到找到所需的数据。
- 目前数据库多采用两级索引的B+树，树的层次最多三层，因此可能需要5次磁盘访问才能更新一条记录（3次磁盘访问获得数据索引以及行ID，然后再进行一次数据文件读操作以及一次数据文件写操作）
LSM树
- 简介：目前许多NoSQL产品采用LSM树作为主要数据结构。LSM树如下图所示。
- LSM树是一个N阶合并树。数据写操作（包括插入、修改、删除）都在内存中进行，并且都会创建一个新记录，这些数据在内存中仍然还是一颗排序树，当数据量超过设定的内存阈值后，会将这颗排序树和磁盘上最新的排序树合并。当这颗排序树的数据量也超过设定阈值后，和磁盘下一级的排序树合并。合并过程中，会用最新更新的数据覆盖旧的数据。
比较
- 在LSM树上进行一次数据更新不需要磁盘访问，在内存即可完成，速度远快于B+树。当数据访问以写操作为主，而读操作则集中在最近写入的数据上时，使用LSM树可以极大程度地减少磁盘的访问次数，加快访问速度。
总结
作为存储结构，B+树不是关系数据库所独有的，NoSQL数据库也可以使用B+树。同理，关系数据库也可以使用LSM。
摘取自《大型网站技术架构》
版权声明：本文为weixin_40460171原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。