LSM-Treecompare.docVIP

这篇文章读起来感觉有难度，细节太多。它介绍了 LSM-Tree 这种算法思想。这种算法思想主要用于解决日志记录索引的问题。这种应用的特点是数据量大、写速率高(2000条/s)，又要建立有效的索引来查找日志中的特定条目。 采用 B+ 树索引，因为数据量大，每次又是随机的写到一个 page 中，导致无法进行有效的 page 缓存，每次写基本上对应两次 I/O，因此不可行。解决思路就是把写操作延迟和批处理化。具体的做法就是写一个条目的时候先写到内存中的数据结构中，然后批量的 merge 到磁盘中的数据结构中。但是内存中的数据结构和磁盘中的数据结构具体是怎么样的，论文中只做了简要的描述。Cassandra 中采用类似的思想，只是采用的数据结构是 SSTable，和论文中说的不一样。 HYPERLINK /macyang/article/details/6677237 Seek (B+ tree) vs. Transfer(LSM tree) 分类： HYPERLINK /macyang/article/category/542398 Database/Nosql HYPERLINK /macyang/article/category/741234 Distributed System2011-08-10 22:57528人阅读 HYPERLINK /macyang/article/details/6677237 \l comments 评论(0) HYPERLINK javascript:void(0); \o 收藏 收藏 HYPERLINK /macyang/article/details/6677237 \l report \o 举报 举报 本文主要介绍了B+ tree和LSM tree，从seek和transfer的角度看Hbase为什么选择了LSM tree，而不是像大多数RDBMS那样使用B+ tree，在Hbase里面LSM tree这种结构其实就是由HLog + Memstore + StoreFile构成，HLog保存了顺序写入磁盘的日志，Memstore能够保存最近的数据，StoreFile负责存储Memstore flush的数据，另外背后有一些服务线程默默的做了很多事情，比如针对store files的compaction, 针对region的split, hlog file的roller等等。 Before we look into the architecture itself, however, we will first address a more fundamental difference between typical RDBMS storage structures and alternative ones. Specifically, we are going to have a quick look into B-trees, or rather B+ trees, as they are commonly used in relational storage engines, and Log-Structured Merge Trees, which (to some extent) form the basis for Bigtables storage architecture, as discussed in the section called “Building Blocks”. [html] HYPERLINK /macyang/article/details/6677237 \o view plain view plain HYPERLINK /macyang/article/details/6677237 \o copy copy HYPERLINK /macyang/article/details/6677237 \o print print HYPERLINK /macyang/article/details/6677237 \o ? ? Note Please note that RDBMSs are not limited to use B-tree type structures, nor do all NoSQL solutions use different architectures. You will find a colorful variety of mix-and-match technologies, but with one common objective: use the best strategy for the prob