src/leveldb/include/leveldb/filter_policy.h

   1 // Copyright (c) 2012 The LevelDB Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   4 //
   5 // A database can be configured with a custom FilterPolicy object.
   6 // This object is responsible for creating a small filter from a set
   7 // of keys.  These filters are stored in leveldb and are consulted
   8 // automatically by leveldb to decide whether or not to read some
   9 // information from disk. In many cases, a filter can cut down the
  10 // number of disk seeks form a handful to a single disk seek per
  11 // DB::Get() call.
  12 //
  13 // Most people will want to use the builtin bloom filter support (see
  14 // NewBloomFilterPolicy() below).
  15
  16 #ifndef STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_
  17 #define STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_
  18
  19 #include <string>
  20
  21 namespace leveldb {
  22
  23 class Slice;
  24
  25 class FilterPolicy {
  26  public:
  27   virtual ~FilterPolicy();
  28
  29   // Return the name of this policy.  Note that if the filter encoding
  30   // changes in an incompatible way, the name returned by this method
  31   // must be changed.  Otherwise, old incompatible filters may be
  32   // passed to methods of this type.
  33   virtual const char* Name() const = 0;
  34
  35   // keys[0,n-1] contains a list of keys (potentially with duplicates)
  36   // that are ordered according to the user supplied comparator.
  37   // Append a filter that summarizes keys[0,n-1] to *dst.
  38   //
  39   // Warning: do not change the initial contents of *dst.  Instead,
  40   // append the newly constructed filter to *dst.
  41   virtual void CreateFilter(const Slice* keys, int n, std::string* dst)
  42       const = 0;
  43
  44   // "filter" contains the data appended by a preceding call to
  45   // CreateFilter() on this class.  This method must return true if
  46   // the key was in the list of keys passed to CreateFilter().
  47   // This method may return true or false if the key was not on the
  48   // list, but it should aim to return false with a high probability.
  49   virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0;
  50 };
  51
  52 // Return a new filter policy that uses a bloom filter with approximately
  53 // the specified number of bits per key.  A good value for bits_per_key
  54 // is 10, which yields a filter with ~ 1% false positive rate.
  55 //
  56 // Callers must delete the result after any database that is using the
  57 // result has been closed.
  58 //
  59 // Note: if you are using a custom comparator that ignores some parts
  60 // of the keys being compared, you must not use NewBloomFilterPolicy()
  61 // and must provide your own FilterPolicy that also ignores the
  62 // corresponding parts of the keys.  For example, if the comparator
  63 // ignores trailing spaces, it would be incorrect to use a
  64 // FilterPolicy (like NewBloomFilterPolicy) that does not ignore
  65 // trailing spaces in keys.
  66 extern const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);
  67
  68 }
  69
  70 #endif  // STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_