summaryrefslogtreecommitdiff
path: root/doc/table_format.txt
diff options
context:
space:
mode:
authorSanjay Ghemawat <sanjay@google.com>2012-04-17 08:36:46 -0700
committerSanjay Ghemawat <sanjay@google.com>2012-04-17 08:36:46 -0700
commit85584d497e7b354853b72f450683d59fcf6b9c5c (patch)
treeb6aad4f973f87487c3caa5600e7596219c79f645 /doc/table_format.txt
parentbc1ee4d25e09b04e074db330a41f54ef4af0e31b (diff)
downloadleveldb-85584d497e7b354853b72f450683d59fcf6b9c5c.tar.gz
Added bloom filter support.v1.4
In particular, we add a new FilterPolicy class. An instance of this class can be supplied in Options when opening a database. If supplied, the instance is used to generate summaries of keys (e.g., a bloom filter) which are placed in sstables. These summaries are consulted by DB::Get() so we can avoid reading sstable blocks that are guaranteed to not contain the key we are looking for. This change provides one implementation of FilterPolicy based on bloom filters. Other changes: - Updated version number to 1.4. - Some build tweaks. - C binding for CompactRange. - A few more benchmarks: deleteseq, deleterandom, readmissing, seekrandom. - Minor .gitignore update.
Diffstat (limited to 'doc/table_format.txt')
-rw-r--r--doc/table_format.txt41
1 files changed, 41 insertions, 0 deletions
diff --git a/doc/table_format.txt b/doc/table_format.txt
index ad5aa4b..d0f3065 100644
--- a/doc/table_format.txt
+++ b/doc/table_format.txt
@@ -47,6 +47,47 @@ the BlockHandle of the metaindex and index blocks as well as a magic number.
// (40==2*BlockHandle::kMaxEncodedLength)
magic: fixed64; // == 0xdb4775248b80fb57
+"filter" Meta Block
+-------------------
+
+If a "FilterPolicy" was specified when the database was opened, a
+filter block is stored in each table. The "metaindex" block contains
+an entry that maps from "filter.<N>" to the BlockHandle for the filter
+block where "<N>" is the string returned by the filter policy's
+"Name()" method.
+
+The filter block stores a sequence of filters, where filter i contains
+the output of FilterPolicy::CreateFilter() on all keys that are stored
+in a block whose file offset falls within the range
+
+ [ i*base ... (i+1)*base-1 ]
+
+Currently, "base" is 2KB. So for example, if blocks X and Y start in
+the range [ 0KB .. 2KB-1 ], all of the keys in X and Y will be
+converted to a filter by calling FilterPolicy::CreateFilter(), and the
+resulting filter will be stored as the first filter in the filter
+block.
+
+The filter block is formatted as follows:
+
+ [filter 0]
+ [filter 1]
+ [filter 2]
+ ...
+ [filter N-1]
+
+ [offset of filter 0] : 4 bytes
+ [offset of filter 1] : 4 bytes
+ [offset of filter 2] : 4 bytes
+ ...
+ [offset of filter N-1] : 4 bytes
+
+ [offset of beginning of offset array] : 4 bytes
+ lg(base) : 1 byte
+
+The offset array at the end of the filter block allows efficient
+mapping from a data block offset to the corresponding filter.
+
"stats" Meta Block
------------------