590
604
class _LeafNode(object):
591
605
"""A leaf node for a serialised B+Tree index."""
607
__slots__ = ('keys', 'min_key', 'max_key')
593
609
def __init__(self, bytes, key_length, ref_list_length):
594
610
"""Parse bytes to create a leaf node object."""
595
611
# splitlines mangles the \r delimiters.. don't use it.
596
self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
597
key_length, ref_list_length))
612
key_list = _btree_serializer._parse_leaf_lines(bytes,
613
key_length, ref_list_length)
615
self.min_key = key_list[0][0]
616
self.max_key = key_list[-1][0]
618
self.min_key = self.max_key = None
619
self.keys = dict(key_list)
600
622
class _InternalNode(object):
601
623
"""An internal node for a serialised B+Tree index."""
625
__slots__ = ('keys', 'offset')
603
627
def __init__(self, bytes):
604
628
"""Parse bytes to create an internal node object."""
605
629
# splitlines mangles the \r delimiters.. don't use it.
1039
1083
output.append(cur_out)
1086
def _walk_through_internal_nodes(self, keys):
1087
"""Take the given set of keys, and find the corresponding LeafNodes.
1089
:param keys: An unsorted iterable of keys to search for
1090
:return: (nodes, index_and_keys)
1091
nodes is a dict mapping {index: LeafNode}
1092
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1094
# 6 seconds spent in miss_torture using the sorted() line.
1095
# Even with out of order disk IO it seems faster not to sort it when
1096
# large queries are being made.
1097
keys_at_index = [(0, sorted(keys))]
1099
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1100
node_indexes = [idx for idx, s_keys in keys_at_index]
1101
nodes = self._get_internal_nodes(node_indexes)
1103
next_nodes_and_keys = []
1104
for node_index, sub_keys in keys_at_index:
1105
node = nodes[node_index]
1106
positions = self._multi_bisect_right(sub_keys, node.keys)
1107
node_offset = next_row_start + node.offset
1108
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1109
for pos, s_keys in positions])
1110
keys_at_index = next_nodes_and_keys
1111
# We should now be at the _LeafNodes
1112
node_indexes = [idx for idx, s_keys in keys_at_index]
1114
# TODO: We may *not* want to always read all the nodes in one
1115
# big go. Consider setting a max size on this.
1116
nodes = self._get_leaf_nodes(node_indexes)
1117
return nodes, keys_at_index
1042
1119
def iter_entries(self, keys):
1043
1120
"""Iterate over keys within the index.
1082
1159
needed_keys = keys
1083
1160
if not needed_keys:
1085
# 6 seconds spent in miss_torture using the sorted() line.
1086
# Even with out of order disk IO it seems faster not to sort it when
1087
# large queries are being made.
1088
needed_keys = sorted(needed_keys)
1090
nodes_and_keys = [(0, needed_keys)]
1092
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1093
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1094
nodes = self._get_internal_nodes(node_indexes)
1096
next_nodes_and_keys = []
1097
for node_index, sub_keys in nodes_and_keys:
1098
node = nodes[node_index]
1099
positions = self._multi_bisect_right(sub_keys, node.keys)
1100
node_offset = next_row_start + node.offset
1101
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1102
for pos, s_keys in positions])
1103
nodes_and_keys = next_nodes_and_keys
1104
# We should now be at the _LeafNodes
1105
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1107
# TODO: We may *not* want to always read all the nodes in one
1108
# big go. Consider setting a max size on this.
1110
nodes = self._get_leaf_nodes(node_indexes)
1162
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1111
1163
for node_index, sub_keys in nodes_and_keys:
1112
1164
if not sub_keys:
1121
1173
yield (self, next_sub_key, value)
1175
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1176
"""Find the parent_map information for the set of keys.
1178
This populates the parent_map dict and missing_keys set based on the
1179
queried keys. It also can fill out an arbitrary number of parents that
1180
it finds while searching for the supplied keys.
1182
It is unlikely that you want to call this directly. See
1183
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1185
:param keys: A keys whose ancestry we want to return
1186
Every key will either end up in 'parent_map' or 'missing_keys'.
1187
:param ref_list_num: This index in the ref_lists is the parents we
1189
:param parent_map: {key: parent_keys} for keys that are present in this
1190
index. This may contain more entries than were in 'keys', that are
1191
reachable ancestors of the keys requested.
1192
:param missing_keys: keys which are known to be missing in this index.
1193
This may include parents that were not directly requested, but we
1194
were able to determine that they are not present in this index.
1195
:return: search_keys parents that were found but not queried to know
1196
if they are missing or present. Callers can re-query this index for
1197
those keys, and they will be placed into parent_map or missing_keys
1199
if not self.key_count():
1200
# We use key_count() to trigger reading the root node and
1201
# determining info about this BTreeGraphIndex
1202
# If we don't have any keys, then everything is missing
1203
missing_keys.update(keys)
1205
if ref_list_num >= self.node_ref_lists:
1206
raise ValueError('No ref list %d, index has %d ref lists'
1207
% (ref_list_num, self.node_ref_lists))
1209
# The main trick we are trying to accomplish is that when we find a
1210
# key listing its parents, we expect that the parent key is also likely
1211
# to sit on the same page. Allowing us to expand parents quickly
1212
# without suffering the full stack of bisecting, etc.
1213
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1215
# These are parent keys which could not be immediately resolved on the
1216
# page where the child was present. Note that we may already be
1217
# searching for that key, and it may actually be present [or known
1218
# missing] on one of the other pages we are reading.
1220
# We could try searching for them in the immediate previous or next
1221
# page. If they occur "later" we could put them in a pending lookup
1222
# set, and then for each node we read thereafter we could check to
1223
# see if they are present.
1224
# However, we don't know the impact of keeping this list of things
1225
# that I'm going to search for every node I come across from here on
1227
# It doesn't handle the case when the parent key is missing on a
1228
# page that we *don't* read. So we already have to handle being
1229
# re-entrant for that.
1230
# Since most keys contain a date string, they are more likely to be
1231
# found earlier in the file than later, but we would know that right
1232
# away (key < min_key), and wouldn't keep searching it on every other
1233
# page that we read.
1234
# Mostly, it is an idea, one which should be benchmarked.
1235
parents_not_on_page = set()
1237
for node_index, sub_keys in nodes_and_keys:
1240
# sub_keys is all of the keys we are looking for that should exist
1241
# on this page, if they aren't here, then they won't be found
1242
node = nodes[node_index]
1243
node_keys = node.keys
1244
parents_to_check = set()
1245
for next_sub_key in sub_keys:
1246
if next_sub_key not in node_keys:
1247
# This one is just not present in the index at all
1248
missing_keys.add(next_sub_key)
1250
value, refs = node_keys[next_sub_key]
1251
parent_keys = refs[ref_list_num]
1252
parent_map[next_sub_key] = parent_keys
1253
parents_to_check.update(parent_keys)
1254
# Don't look for things we've already found
1255
parents_to_check = parents_to_check.difference(parent_map)
1256
# this can be used to test the benefit of having the check loop
1258
# parents_not_on_page.update(parents_to_check)
1260
while parents_to_check:
1261
next_parents_to_check = set()
1262
for key in parents_to_check:
1263
if key in node_keys:
1264
value, refs = node_keys[key]
1265
parent_keys = refs[ref_list_num]
1266
parent_map[key] = parent_keys
1267
next_parents_to_check.update(parent_keys)
1269
# This parent either is genuinely missing, or should be
1270
# found on another page. Perf test whether it is better
1271
# to check if this node should fit on this page or not.
1272
# in the 'everything-in-one-pack' scenario, this *not*
1273
# doing the check is 237ms vs 243ms.
1274
# So slightly better, but I assume the standard 'lots
1275
# of packs' is going to show a reasonable improvement
1276
# from the check, because it avoids 'going around
1277
# again' for everything that is in another index
1278
# parents_not_on_page.add(key)
1279
# Missing for some reason
1280
if key < node.min_key:
1281
# in the case of bzr.dev, 3.4k/5.3k misses are
1282
# 'earlier' misses (65%)
1283
parents_not_on_page.add(key)
1284
elif key > node.max_key:
1285
# This parent key would be present on a different
1287
parents_not_on_page.add(key)
1289
# assert key != node.min_key and key != node.max_key
1290
# If it was going to be present, it would be on
1291
# *this* page, so mark it missing.
1292
missing_keys.add(key)
1293
parents_to_check = next_parents_to_check.difference(parent_map)
1294
# Might want to do another .difference() from missing_keys
1295
# parents_not_on_page could have been found on a different page, or be
1296
# known to be missing. So cull out everything that has already been
1298
search_keys = parents_not_on_page.difference(
1299
parent_map).difference(missing_keys)
1123
1302
def iter_entries_prefix(self, keys):
1124
1303
"""Iterate over keys within the index using prefix matching.
added
removed
bzrlib/btree_index.py
