public Searcher(FullTextIndex index)
        {
            _index = index;
            _tx = _index.StorageEnvironment.NewTransaction(TransactionFlags.Read);

            _docs = _tx.ReadTree("Docs");
        }

 public PageSplitter(Transaction tx,
     Tree tree,
     SliceComparer cmp,
     Slice newKey,
     int len,
     long pageNumber,
     NodeFlags nodeType,
     ushort nodeVersion,
     Cursor cursor,
     TreeMutableState treeState)
 {
     _tx = tx;
     _tree = tree;
     _cmp = cmp;
     _newKey = newKey;
     _len = len;
     _pageNumber = pageNumber;
     _nodeType = nodeType;
     _nodeVersion = nodeVersion;
     _cursor = cursor;
     _treeState = treeState;
     Page page = _cursor.Pages.First.Value;
     _page = tx.ModifyPage(page.PageNumber, page);
     _cursor.Pop();
 }

 public StorageEnvironmentState(Tree freeSpaceRoot, Tree root, long nextPageNumber)
 {
     if (freeSpaceRoot != null)
         FreeSpaceRoot = freeSpaceRoot.State;
     if (root != null)
         Root = root.State;
     NextPageNumber = nextPageNumber;
 }

 public ParentPageAction(Page parentPage, Page currentPage, Tree tree, Cursor cursor, Transaction tx)
 {
     _parentPage = parentPage;
     _currentPage = currentPage;
     _tree = tree;
     _cursor = cursor;
     _tx = tx;
 }

		public TreeIterator(Tree tree, Transaction tx)
		{
			_tree = tree;
			_tx = tx;

			if (tree.KeysPrefixing)
				_currentInternalKey = new PrefixedSlice(SliceOptions.Key);
			else
				_currentInternalKey = new Slice(SliceOptions.Key); 
		}

        protected override void Init()
        {
            _fieldTree = Transaction.ReadTree("@fld_" + _field);
            if (_fieldTree == null)
                return;

            var termFreqInDocs = _fieldTree.State.EntriesCount;
            var numberOfDocs = Transaction.ReadTree("$metadata").Read(Transaction, "docs").Reader.ReadInt64();

            var idf = Index.Conventions.Idf(termFreqInDocs, numberOfDocs);
            _weight = idf*idf;
        }

        protected override void Init()
        {
            base.Init();

            _positionsTree = Transaction.ReadTree("TermPositions");
            _docsTree = Transaction.ReadTree("Docs");

            _fieldId = Index.GetFieldNumber(Field);
            _prefix = new byte[FullTextIndex.FieldDocumentSize];
            _prefixSlice = new Slice(_prefix);

            _maxKey = new byte[FullTextIndex.FieldDocumentSize];
            _maxKeySlice = new Slice(_maxKey);
        }

		public static Tree Create(Transaction tx, SliceComparer cmp, TreeFlags flags = TreeFlags.None)
		{
			var newRootPage = NewPage(tx, PageFlags.Leaf, 1);
			var tree = new Tree(cmp, newRootPage.PageNumber)
			{
				_state =
				{
					Depth = 1,
					Flags = flags,
                    InWriteTransaction = true
				}
			};
			
			tree.State.RecordNewPage(newRootPage, 1);
			return tree;
		}

        public static Tree Create(Transaction tx, bool keysPrefixing, TreeFlags flags = TreeFlags.None)
        {
            var newRootPage = NewPage(tx, keysPrefixing ? PageFlags.Leaf | PageFlags.KeysPrefixed : PageFlags.Leaf, 1);
            var tree = new Tree(tx, newRootPage.PageNumber)
            {
                _state =
                {
                    Depth = 1,
                    Flags = flags,
                    InWriteTransaction = true,
                    KeysPrefixing = keysPrefixing
                }
            };

            tree.State.RecordNewPage(newRootPage, 1);
            return tree;
        }

 public unsafe List<Slice> Keys(Tree t, Transaction tx)
 {
     var results = new List<Slice>();
     using (var it = t.Iterate())
     {
         if (it.Seek(Slice.BeforeAllKeys) == false)
             return results;
         do
         {
             results.Add(it.CurrentKey);
         } while (it.MoveNext());
     }
     return results;
 }

		protected void RenderAndShow(Transaction tx, Tree root, int showEntries = 25)
		{
			if (Debugger.IsAttached == false)
				return;
			var path = Path.Combine(Environment.CurrentDirectory, "test-tree.dot");
			var rootPageNumber = tx.Environment.State.GetTree(tx,root.Name).State.RootPageNumber;
			TreeDumper.Dump(tx, path, tx.GetReadOnlyPage(rootPageNumber), showEntries);

			var output = Path.Combine(Environment.CurrentDirectory, "output.svg");
			var p = Process.Start(DebugStuff.FindGraphviz() + @"\bin\dot.exe", "-Tsvg  " + path + " -o " + output);
			p.WaitForExit();
			Process.Start(output);
		}

 public StorageEnvironmentState(Tree freeSpaceRoot, Tree root, long nextPageNumber)
 {
     FreeSpaceRoot = freeSpaceRoot;
     Root = root;
     NextPageNumber = nextPageNumber;
 }

		internal bool TryRemoveMultiValueTree(Tree parentTree, MemorySlice key)
		{
			var keyToRemove = Tuple.Create(parentTree, key);
			if (_multiValueTrees == null || !_multiValueTrees.ContainsKey(keyToRemove))
				return false;

			return _multiValueTrees.Remove(keyToRemove);
		}

		internal Page ModifyPage(long num, Tree tree, Page page)
		{
			_env.AssertFlushingNotFailed();

			page = page ?? GetReadOnlyPage(num);
			if (page.Dirty)
				return page;

			if (_dirtyPages.Contains(num))
			{
				page.Dirty = true;
				return page;
			}

		    var newPage = AllocatePage(1, PageFlags.None, num); // allocate new page in a log file but with the same number

            Memory.Copy(newPage.Base, page.Base, AbstractPager.PageSize);
			newPage.LastSearchPosition = page.LastSearchPosition;
			newPage.LastMatch = page.LastMatch;
			tree.RecentlyFoundPages.Reset(num);

			return newPage;
		}

		internal void AddMultiValueTree(Tree tree, MemorySlice key, Tree mvTree)
		{
			if (_multiValueTrees == null)
				_multiValueTrees = new Dictionary<Tuple<Tree, MemorySlice>, Tree>(new TreeAndSliceComparer());
			mvTree.IsMultiValueTree = true;
			_multiValueTrees.Add(Tuple.Create(tree, key), mvTree);
		}

		internal void UpdateRootsIfNeeded(Tree root, Tree freeSpace)
		{
			//can only happen during initial transaction that creates Root and FreeSpaceRoot trees
			if (State.Root == null && State.FreeSpaceRoot == null)
			{
				State.Root = root;
				State.FreeSpaceRoot = freeSpace;
			}
		}

        public TreeRebalancer(Transaction tx, Tree tree, Cursor cursor)
        {
            _tx = tx;
			_tree = tree;
	        _cursor = cursor;
        }

		private static long ReadIsTopologyChanged(Tree metadata)
		{
			var readResult = metadata.Read("current-topology-index");
			if (readResult == null)
				return -1;

			return readResult.Reader.ReadLittleEndianInt64();
		}

		private static long GetLastEntryNumber(Tree logs, Transaction tx)
		{
			long lastEntry;
			var lastKey = logs.LastKeyOrDefault();
			if (lastKey != null)
			{
				lastEntry = lastKey.CreateReader().ReadBigEndianInt64();
			}
			else
			{
				var metadata = tx.ReadTree(MetadataTreeName);
				// maybe there is a snapshot?
				var snapshotIndex = metadata.Read("snapshot-index");
				if (snapshotIndex != null)
					lastEntry = snapshotIndex.Reader.ReadLittleEndianInt64();
				else
					lastEntry = 0;
			}
			return lastEntry;
		}

        private OverflowsAddResult AddOverflows(Transaction tx, Tree tree, int treeNumber, Random r)
        {
            var minOverflowSize = AbstractPager.NodeMaxSize - Constants.PageHeaderSize + 1;
            var entriesAdded = new List<string>();
            var overflowsAdded = 0;

            for (int j = 0; j < treeNumber; j++)
            {
                var overflowSize = r.Next(minOverflowSize, 10000);
                string key = "overflow_" + j;
                tree.Add(key, new MemoryStream(new byte[overflowSize]));

                entriesAdded.Add(key);
                overflowsAdded += tx.DataPager.GetNumberOfOverflowPages(overflowSize);
            }

            return new OverflowsAddResult
            {
                AddedEntries = entriesAdded,
                NumberOfOverflowPages = overflowsAdded
            };
        }