/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2008-10-14 21:35:27 UTC
  • mto: This revision was merged to the branch mainline in revision 3805.
  • Revision ID: john@arbash-meinel.com-20081014213527-4j9uc93aq1qmn43b
Add in a shortcut when we haven't cached much yet.

Document the current algorithm more completely, including the proper
justification for the various steps.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
700
700
        # getting.
701
701
        cached_keys = self._get_cached_keys()
702
702
 
703
 
        # if len(cached_keys) < 2:
704
 
        #     # We haven't read enough to justify expansion
705
 
        #     return node_indexes
706
 
 
707
703
        # If reading recommended_pages would read the rest of the index, just
708
704
        # do so.
709
705
        if num_pages - len(cached_keys) <= self._recommended_pages:
717
713
                trace.mutter('  reading all unread pages: %s', expanded)
718
714
            return expanded
719
715
 
720
 
        needed_nodes = self._recommended_pages - len(node_indexes)
721
 
        final_nodes = set(node_indexes)
722
716
        if self._root_node is None:
723
717
            # ATM on the first read of the root node of a large index, we don't
724
718
            # bother pre-reading any other pages. This is because the
728
722
            # layer index is small
729
723
            final_nodes = node_indexes
730
724
        else:
 
725
            tree_depth = len(self._row_lengths)
 
726
            if len(cached_keys) < tree_depth and len(node_indexes) == 1:
 
727
                # We haven't read enough to justify expansion
 
728
                # If we are only going to read the root node, and 1 leaf node,
 
729
                # then it isn't worth expanding our request. Once we've read at
 
730
                # least 2 nodes, then we are probably doing a search, and we
 
731
                # start expanding our requests.
 
732
                if 'index' in debug.debug_flags:
 
733
                    trace.mutter('  not expanding on first reads')
 
734
                return node_indexes
 
735
 
731
736
            # Expand requests to neighbors until we have at least
732
737
            # recommended_pages to request. We only want to expand requests
733
738
            # within a given layer. We cheat a little bit and assume all
734
739
            # requests will be in the same layer. This is true given the
735
740
            # current design, but if it changes this algorithm may perform
736
741
            # oddly.
 
742
            final_nodes = set(node_indexes)
737
743
            first = end = None
738
744
            new_tips = set(final_nodes)
739
745
            while len(final_nodes) < self._recommended_pages and new_tips: