public byte[] Retrieve(ulong pageId, BrightstarProfiler profiler)
 {
     using (profiler.Step("PageStore.Retrieve"))
     {
         if (!_readonly && pageId >= _newPageOffset)
         {
             var newPage = _newPages[(int) (pageId - _newPageOffset)];
             return newPage.Data;
         }
         var page = PageCache.Instance.Lookup(_path, pageId) as FilePage;
         if (page != null)
         {
             profiler.Incr("PageCache Hit");
             return page.Data;
         }
         using (profiler.Step("Load Page"))
         {
             profiler.Incr("PageCache Miss");
             using (profiler.Step("Create FilePage"))
             {
                 // Lock on stream to prevent attempts to concurrently load a page
                 lock (_stream)
                 {
                     page = new FilePage(_stream, pageId, _pageSize);
                 }
             }
             using (profiler.Step("Add FilePage To Cache"))
             {
                 PageCache.Instance.InsertOrUpdate(_path, page);
             }
             return page.Data;
         }
     }
 }

        public INode GetNode(ulong nodeId, BrightstarProfiler profiler)
        {
            using (profiler.Step("BPlusTree.GetNode"))
            {
                INode ret;
                if (_nodeCache.TryGetValue(nodeId, out ret))
                {
                    profiler.Incr("NodeCache Hit");
                    return ret;
                }

                profiler.Incr("NodeCache Miss");
                using (profiler.Step("Load Node"))
                {
                    var nodePage = _pageStore.Retrieve(nodeId, profiler);
                    var header = BitConverter.ToInt32(nodePage.Data, 0);
                    if (header < 0)
                    {
                        ret = MakeInternalNode(nodePage, ~header);
#if DEBUG_BTREE
                        _config.BTreeDebug("{0}: Loaded INTERNAL node from page {1}. {2}",_config.DebugId, nodePage.Id, ret.ToString());
#endif
                    }
                    else
                    {
                        ret = MakeLeafNode(nodePage, header);
#if DEBUG_BTREE
                        _config.BTreeDebug("{0}: Loaded LEAF node from page {1}. {2}", _config.DebugId, nodePage.Id, ret.ToString());
#endif
                    }
                    _nodeCache.Add(ret);
                    return ret;
                }
            }
        }

 private IResource CreateLongUriResource(ulong txnId, string uri, BrightstarProfiler profiler)
 {
     ulong pageId;
     byte segId;
     _resourceTable.Insert(txnId, uri, out pageId, out segId, profiler);
     return new LongUriResource(uri, pageId, segId);
 }

 /// <summary>
 /// Opens an existing tree in the page store
 /// </summary>
 /// <param name="pageStore"></param>
 /// <param name="rootPageId">The page ID of the BTree root node</param>
 /// <param name="keySize"></param>
 /// <param name="dataSize"></param>
 /// <param name="profiler"></param>
 public BPlusTree(IPageStore pageStore, ulong rootPageId, int keySize = 8, int dataSize = 64, BrightstarProfiler profiler = null)
 {
     _config = new BPlusTreeConfiguration(pageStore, keySize, dataSize, pageStore.PageSize);
     _pageStore = pageStore;
     var root = GetNode(rootPageId, profiler);
     _rootId = root.PageId;
 }

        public void TestSimpleJoinQuery()
        {
            var sparqlQuery =
                    @"PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/> 
                    SELECT ?review WHERE { 
                        ?review bsbm:reviewFor ?product . 
                        ?product bsbm:productFeature <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/instances/ProductFeature2330> .
                    } LIMIT 3";
            // Warm-up
            var client = BrightstarService.GetClient("type=embedded;storesDirectory=stores");
            for (int i = 0; i < 5; i++)
            {
                client.ExecuteQuery("SparqlPerformance", sparqlQuery);
            }

            // Profile
            var profiler = new BrightstarProfiler("SimpleJoinQuery");
            for (int i = 0; i < 1000; i++)
            {
                using (profiler.Step("ExecuteQuery"))
                {
                    client.ExecuteQuery("SparqlPerformance", sparqlQuery);
                }
            }

            Console.WriteLine(profiler.GetLogString());
        }

 public void Insert(ulong transactionId, string resource, out ulong pageId, out byte segmentId, BrightstarProfiler profiler)
 {
     using (profiler.Step("ResourceTable.Insert"))
     {
         var byteCount = Encoding.UTF8.GetByteCount(resource);
         var resourceBytes = new byte[byteCount + 4];
         BitConverter.GetBytes(byteCount).CopyTo(resourceBytes, 0);
         Encoding.UTF8.GetBytes(resource, 0, resource.Length, resourceBytes, 4);
         lock (_writeLock)
         {
             if (_nextSegment == _pointerSegment)
             {
                 StartNewPage(transactionId, profiler);
             }
             pageId = _currentPage;
             segmentId = _nextSegment;
             for (int i = 0; i < (byteCount + 4); i += _segmentSize)
             {
                 _pageStore.Write(transactionId, _currentPage, resourceBytes, i, _nextSegment*_segmentSize,
                                  _segmentSize < (byteCount + 4 - i) ? _segmentSize : (byteCount + 4 - i),
                                  profiler);
                 _nextSegment++;
                 if (_nextSegment == _pointerSegment)
                 {
                     StartNewPage(transactionId, profiler);
                 }
             }
         }
     }
 }

        private IEnumerable<KeyValuePair<byte[], ulong>>MakeInternalNodes(ulong txnId, IEnumerable<KeyValuePair<byte[], ulong >> children, BrightstarProfiler profiler)
        {
            var enumerator = children.GetEnumerator();
            var childList = enumerator.Next(_internalBranchFactor).ToList();
            if (childList.Count == 1)
            {
                yield return childList[0];
                yield break;
            }

            byte[] prevNodeKey = childList[0].Key;
            IInternalNode prevNode = MakeInternalNode(txnId, childList);
            childList = enumerator.Next(_internalBranchFactor).ToList();
            while(childList.Count > 0)
            {
                IInternalNode nextNode = MakeInternalNode(txnId, childList);
                var nextNodeKey = childList[0].Key;
                if (nextNode.NeedJoin)
                {
                    nextNodeKey = new byte[_config.KeySize];
                    nextNode.RedistributeFromLeft(txnId, prevNode, childList[0].Key, nextNodeKey);
                }
                yield return WriteNode(txnId, prevNode, prevNodeKey, profiler);
                prevNode = nextNode;
                prevNodeKey = nextNodeKey;
                childList = enumerator.Next(_internalBranchFactor).ToList();
            }
            
            yield return WriteNode(txnId, prevNode, prevNodeKey, profiler);
        }

        public INode GetNode(ulong nodeId, BrightstarProfiler profiler)
        {
            using (profiler.Step("BPlusTree.GetNode"))
            {
                INode ret;
                if (_modifiedNodes.TryGetValue(nodeId, out ret))
                {
                    profiler.Incr("NodeCache Hit");
                    return ret;
                }
                if (_nodeCache.TryGetValue(nodeId, out ret))
                {
                    profiler.Incr("NodeCache Hit");
                    return ret;
                }

                profiler.Incr("NodeCache Miss");
                using (profiler.Step("Load Node"))
                {
                    var nodePage = _pageStore.Retrieve(nodeId, profiler);
                    var header = BitConverter.ToInt32(nodePage, 0);
                    if (header < 0)
                    {
                        ret = new InternalNode(nodeId, nodePage, ~header, _config);
                    }
                    else
                    {
                        ret = new LeafNode(nodeId, nodePage, header, _config);
                    }
                    _nodeCache.Add(ret);
                    return ret;
                }
            }
        }

 /// <summary>
 /// Retrieve the resource at the specified page and segment offset
 /// </summary>
 /// <param name="pageId">The ID of the page that holds the resource to be retrieved</param>
 /// <param name="segment">The index of the segment within the page that holds the start of the resource</param>
 /// <param name="profiler"></param>
 /// <returns>The resource</returns>
 public string GetResource(ulong pageId, byte segment, BrightstarProfiler profiler)
 {
     using (profiler.Step("ResourceTable.GetResource"))
     {
         var currentPage = _pageStore.Retrieve(pageId, profiler);
         int resourceLength = BitConverter.ToInt32(currentPage, segment*_segmentSize);
         int totalLength = resourceLength + 4;
         int segmentsToLoad = totalLength/_segmentSize;
         if (totalLength%_segmentSize > 0) segmentsToLoad++;
         var buffer = new byte[segmentsToLoad*_segmentSize];
         byte segmentIndex = segment;
         for (int i = 0; i < segmentsToLoad; i++)
         {
             if (segmentIndex == _pointerSegment)
             {
                 ulong nextPageId = BitConverter.ToUInt64(currentPage, _pageStore.PageSize - 8);
                 currentPage = _pageStore.Retrieve(nextPageId, profiler);
                 segmentIndex = 0;
             }
             Array.Copy(currentPage, segmentIndex*_segmentSize, buffer, i*_segmentSize, _segmentSize);
             segmentIndex++;
         }
         return Encoding.UTF8.GetString(buffer, 4, resourceLength);
     }
 }

 private IResource CreateLongLiteralResource(ulong txnId, string resourceValue, ulong dataTypeId, ulong langCodeId, BrightstarProfiler profiler)
 {
     ulong pageId;
     byte segId;
     _resourceTable.Insert(txnId, resourceValue, out pageId, out segId, profiler);
     return new LongLiteralResource(resourceValue, dataTypeId, langCodeId, pageId, segId);
 }

 /// <summary>
 /// Creates a new store writing triple sink
 /// </summary>
 /// <param name="writeStore">The store to add the triples to</param>
 /// <param name="jobId">The unique identifier of the job that is writing to the store. May be Guid.Empty if the write is not part of any job.</param>
 /// <param name="batchSize">Number of triples to insert per batch</param>
 /// <param name="commitEachBatch">If true, then the inserts are committed to the store after each batch; if false then the server memory load is checked at the end of each batch and inserts are flushed only if the load exceeds a threshold (currently 80% of available physical RAM).</param>
 /// <param name="profiler"></param>
 public StoreTripleSink(IStore writeStore, Guid jobId, int batchSize = 10000, bool commitEachBatch = false, BrightstarProfiler profiler = null)
 {
     _batchSize = batchSize;
     _store = writeStore;
     _jobId = jobId;
     _commitEachBatch = commitEachBatch;
     _profiler = profiler;
 }

 public ulong Build(ulong txnId, IEnumerable<KeyValuePair<byte[], byte []>> orderedValues, BrightstarProfiler profiler = null)
 {
     var nodeList = MakeInternalNodes(txnId, MakeLeafNodes(txnId, orderedValues.GetEnumerator(), profiler), profiler).ToList();
     while(nodeList.Count > 1)
     {
         nodeList = MakeInternalNodes(txnId, nodeList, profiler).ToList();
     }
     return nodeList[0].Value;
 }

 /// <summary>
 /// Opens an existing tree in the page store
 /// </summary>
 /// <param name="pageStore"></param>
 /// <param name="rootPageId">The page ID of the BTree root node</param>
 /// <param name="keySize"></param>
 /// <param name="dataSize"></param>
 /// <param name="profiler"></param>
 public BPlusTree(IPageStore pageStore, ulong rootPageId, int keySize = 8, int dataSize = 64, BrightstarProfiler profiler = null)
 {
     _config = new BPlusTreeConfiguration(keySize, dataSize, pageStore.PageSize);
     _pageStore = pageStore;
     _modifiedNodes = new Dictionary<ulong, INode>();
     _nodeCache = new WeakReferenceNodeCache();
     _root = GetNode(rootPageId, profiler);
     _nodeCache.Add(_root);
 }

 public ConcurrentGraphIndex(IPageStore pageStore, ulong rootPage, BrightstarProfiler profiler)
 {
     using (profiler.Step("Load ConcurrentGraphIndex"))
     {
         _pageStore = pageStore;
         _graphUriIndex = new Dictionary<string, int>();
         _allEntries = new List<GraphIndexEntry>();
         Read(rootPage, profiler);
     }
 }

 public Store(string storeLocation, IPageStore dataPageStore, IResourceTable resourceTable, ulong storePageId, BrightstarProfiler profiler)
 {
     using (profiler.Step("Load Store"))
     {
         DirectoryPath = storeLocation;
         _pageStore = dataPageStore;
         _resourceTable = resourceTable;
         var storePage = _pageStore.Retrieve(storePageId, profiler);
         Load(storePage, profiler);
     }
 }

 public static IPageStore OpenPageStore(string fileName, bool readOnly, PersistenceType persistenceType = PersistenceType.AppendOnly, ulong txnId = 1UL, BrightstarProfiler profiler = null)
 {
     using (profiler.Step("Open Page Store"))
     {
         if (persistenceType == PersistenceType.AppendOnly)
         {
             return new AppendOnlyFilePageStore(PersistenceManager, fileName, 4096, readOnly, false);
         }
         return new BinaryFilePageStore(PersistenceManager, fileName, 4096, readOnly, txnId);
     }
 }

 public IResource CreateNew(ulong txnId, string resourceValue, bool isLiteral, ulong dataTypeId, ulong langCodeId, BrightstarProfiler profiler)
 {
     var valueLength = Encoding.UTF8.GetByteCount(resourceValue);
     if (isLiteral)
     {
         return valueLength <= MaxLocalLiteralLength
                    ? new ShortLiteralResource(resourceValue, dataTypeId, langCodeId)
                    : CreateLongLiteralResource(txnId, resourceValue, dataTypeId, langCodeId, profiler);
     }
     return valueLength < MaxLocalUriLength
                ? new ShortUriResource(resourceValue)
                : CreateLongUriResource(txnId, resourceValue, profiler);
 }

        public override void Run()
        {
            try
            {
                Logging.LogInfo("Import job being run on file " + _contentFileName);
                StoreWorker.TransactionLog.LogStartTransaction(this);

                var parser = GetParser(_contentFileName);
                var storeDirectory = StoreWorker.WriteStore.DirectoryPath;
                var filePath = Path.Combine(storeDirectory,
                                            ".." + Path.DirectorySeparatorChar + "import" + Path.DirectorySeparatorChar +
                                            _contentFileName);
                var profiler = new BrightstarProfiler("Import " + _contentFileName); // TODO : Conditionally create this if profiling is enabled
                Logging.LogDebug("Import file path calculated as '{0}'", filePath);
                if (!File.Exists(filePath))
                {
                    ErrorMessage = String.Format("Cannot find file {0} in import directory", _contentFileName);
                    throw new FileNotFoundException(ErrorMessage);
                }
                using (_fileStream = new FileStream(filePath, FileMode.Open, FileAccess.Read))
                {
                    _importTripleSink = new StoreTripleSink(StoreWorker.WriteStore, JobId,
                                                            Configuration.TransactionFlushTripleCount,
                                                            profiler:profiler);
                    parser.Parse(_fileStream, this, _graphUri);
                }
                StoreWorker.WriteStore.Commit(JobId, profiler);
                StoreWorker.InvalidateReadStore();

                Logging.LogInfo("Import job completed successfully for " + _contentFileName);
                if (profiler != null)
                {
                    Logging.LogInfo(profiler.GetLogString());
                }
                StoreWorker.TransactionLog.LogEndSuccessfulTransaction(this);
            }
            catch (RdfParserException parserException)
            {
                ErrorMessage = parserException.Message;
                ExceptionDetail = new ExceptionDetail(parserException);
                Logging.LogInfo("Parser error processing import job on file " + _contentFileName + ". " + parserException.Message);
                throw;
            }
            catch (Exception ex)
            {
                ErrorMessage = "Error importing file " + _contentFileName + ". " + ex.Message;
                StoreWorker.TransactionLog.LogEndFailedTransaction(this);
                Logging.LogInfo("Error processing import job on file " + _contentFileName + ". Error Message: " + ex.Message + " Stack trace: " + ex.StackTrace);
                throw;
            }
        }

 public static IPageStore CreateEmptyPageStore(string fileName, PersistenceType persistenceType = PersistenceType.AppendOnly, BrightstarProfiler profiler = null)
 {
     using (profiler.Step("Create Empty Page Store"))
     {
         using (profiler.Step("Delete Existing"))
         {
             if (PersistenceManager.FileExists(fileName)) PersistenceManager.DeleteFile(fileName);
             //if (File.Exists(fileName)) File.Delete(fileName);
         }
         using (profiler.Step("Create New Page Store"))
         {
             if (persistenceType == PersistenceType.AppendOnly)
             {
                 return new AppendOnlyFilePageStore(PersistenceManager, fileName, 4096, false, false);
             }
             return new BinaryFilePageStore(PersistenceManager, fileName, 4096, false, 1);
         }
     }
 }

 /// <summary>
 /// Adds a related resource index entry
 /// </summary>
 /// <param name="txnId"> </param>
 /// <param name="resourceId">The resource ID of the "start" resource</param>
 /// <param name="predicateId">The resource ID of the predicate that relates the resources</param>
 /// <param name="relatedResourceId">The resource ID of the "related" resource</param>
 /// <param name="graphId">The resource ID of the graph containing the relationship</param>
 /// <param name="profiler"></param>
 public void AddRelatedResource(ulong txnId, ulong resourceId, ulong predicateId, ulong relatedResourceId, int graphId, BrightstarProfiler profiler = null)
 {
     using (profiler.Step("Add Related Resource"))
     {
         var predicateIndex = AssertPredicateIndex(txnId, predicateId, profiler);
         var key = MakePredicateIndexKey(resourceId, graphId, relatedResourceId);
         try
         {
             using (profiler.Step("Insert Into Predicate Index"))
             {
                 predicateIndex.Insert(txnId, key, null, profiler: profiler);
             }
         }
         catch (DuplicateKeyException)
         {
             // Ignore duplicate key exceptions 
         }
     }
 }