]>
git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/db/file_indexer.h
1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under the BSD-style license found in the
3 // LICENSE file in the root directory of this source tree. An additional grant
4 // of patent rights can be found in the PATENTS file in the same directory.
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
15 #include "port/port.h"
16 #include "util/arena.h"
17 #include "util/autovector.h"
23 struct FdWithKeyRange
;
26 // The file tree structure in Version is prebuilt and the range of each file
27 // is known. On Version::Get(), it uses binary search to find a potential file
28 // and then check if a target key can be found in the file by comparing the key
29 // to each file's smallest and largest key. The results of these comparisons
30 // can be reused beyond checking if a key falls into a file's range.
31 // With some pre-calculated knowledge, each key comparison that has been done
32 // can serve as a hint to narrow down further searches: if a key compared to
33 // be smaller than a file's smallest or largest, that comparison can be used
34 // to find out the right bound of next binary search. Similarly, if a key
35 // compared to be larger than a file's smallest or largest, it can be utilized
36 // to find out the left bound of next binary search.
37 // With these hints: it can greatly reduce the range of binary search,
38 // especially for bottom levels, given that one file most likely overlaps with
39 // only N files from level below (where N is max_bytes_for_level_multiplier).
40 // So on level L, we will only look at ~N files instead of N^L files on the
44 explicit FileIndexer(const Comparator
* ucmp
);
46 size_t NumLevelIndex() const;
48 size_t LevelIndexSize(size_t level
) const;
50 // Return a file index range in the next level to search for a key based on
51 // smallest and largest key comparison for the current file specified by
52 // level and file_index. When *left_index < *right_index, both index should
53 // be valid and fit in the vector size.
54 void GetNextLevelIndex(const size_t level
, const size_t file_index
,
55 const int cmp_smallest
, const int cmp_largest
,
56 int32_t* left_bound
, int32_t* right_bound
) const;
58 void UpdateIndex(Arena
* arena
, const size_t num_levels
,
59 std::vector
<FileMetaData
*>* const files
);
62 // MSVC version 1800 still does not have constexpr for ::max()
63 kLevelMaxIndex
= rocksdb::port::kMaxInt32
68 const Comparator
* ucmp_
;
72 : smallest_lb(0), largest_lb(0), smallest_rb(-1), largest_rb(-1) {}
73 // During file search, a key is compared against smallest and largest
74 // from a FileMetaData. It can have 3 possible outcomes:
75 // (1) key is smaller than smallest, implying it is also smaller than
76 // larger. Precalculated index based on "smallest < smallest" can
77 // be used to provide right bound.
78 // (2) key is in between smallest and largest.
79 // Precalculated index based on "smallest > greatest" can be used to
80 // provide left bound.
81 // Precalculated index based on "largest < smallest" can be used to
82 // provide right bound.
83 // (3) key is larger than largest, implying it is also larger than smallest.
84 // Precalculated index based on "largest > largest" can be used to
85 // provide left bound.
87 // As a result, we will need to do:
88 // Compare smallest (<=) and largest keys from upper level file with
89 // smallest key from lower level to get a right bound.
90 // Compare smallest (>=) and largest keys from upper level file with
91 // largest key from lower level to get a left bound.
95 // level 2: [1 - 40], [45 - 55], [58 - 80]
96 // A key 35, compared to be less than 50, 3rd file on level 2 can be
97 // skipped according to rule (1). LB = 0, RB = 1.
98 // A key 53, sits in the middle 50 and 60. 1st file on level 2 can be
99 // skipped according to rule (2)-a, but the 3rd file cannot be skipped
100 // because 60 is greater than 58. LB = 1, RB = 2.
101 // A key 70, compared to be larger than 60. 1st and 2nd file can be skipped
102 // according to rule (3). LB = 2, RB = 2.
104 // Point to a left most file in a lower level that may contain a key,
105 // which compares greater than smallest of a FileMetaData (upper level)
107 // Point to a left most file in a lower level that may contain a key,
108 // which compares greater than largest of a FileMetaData (upper level)
110 // Point to a right most file in a lower level that may contain a key,
111 // which compares smaller than smallest of a FileMetaData (upper level)
113 // Point to a right most file in a lower level that may contain a key,
114 // which compares smaller than largest of a FileMetaData (upper level)
118 // Data structure to store IndexUnits in a whole level
121 IndexUnit
* index_units
;
123 IndexLevel() : num_index(0), index_units(nullptr) {}
127 const std::vector
<FileMetaData
*>& upper_files
,
128 const std::vector
<FileMetaData
*>& lower_files
, IndexLevel
* index_level
,
129 std::function
<int(const FileMetaData
*, const FileMetaData
*)> cmp_op
,
130 std::function
<void(IndexUnit
*, int32_t)> set_index
);
133 const std::vector
<FileMetaData
*>& upper_files
,
134 const std::vector
<FileMetaData
*>& lower_files
, IndexLevel
* index_level
,
135 std::function
<int(const FileMetaData
*, const FileMetaData
*)> cmp_op
,
136 std::function
<void(IndexUnit
*, int32_t)> set_index
);
138 autovector
<IndexLevel
> next_level_index_
;
142 } // namespace rocksdb