Thank you so much for your help, my understanding for TDB got a lot better!
One question left : In SPO etc. are the keys in the leaf blocks sorted by growing order of NodeIDs ? So first sorted by Subject NodeIDs, then Predicate and lastly Object NodeIDs (for SPO) . In this case one leaf block of branching factor 4 would look like this : | (2, 1, 4) , (2, 3, 4) , (5, 1, 6) | , where the NodeIDs: "2" and "5" represent RDF Subjects, "1","3" Predicates, "4" and "6" RDF Objects (great simplification of NodeIDs in this example). Thank you for your help! Dennis Grinwald ________________________________ From: Andy Seaborne <[email protected]> Sent: Thursday, May 25, 2017 6:42:22 AM To: [email protected] Subject: Re: B+-Tree Indexing On 24/05/17 17:56, Dennis Grinwald wrote: > Hi Andy, > > > thank you for your quick and helpful response. > > My understanding now is, that every single Node(RDF term) is represented > by a NodeID in TDB. Some NodeIDs contain inlined values in their bottom > 56 bits and others an address, which points to an 56 bit sequence on > disk (Node Table), The 56 bits in the NodeId is the file offset in nodes.dat for the bytes (variable length) for the node (it's a Turtle-ish string in TDB1, RDF Thrift in TDB2 : some bytes that go bytes -> Node). > where details of the node are recorded. The top 8 > bits represent the type. Does that include an unique id, which makes it > possible for the NodeID to be accessed by TDB? NodeIds are internal to TDB. They are on-disk as 8 bytes - they are created in-memeory by setting those bytes. See the code for NodeId.java. > Furthermore I would like to know, what some indexes, when creating a TDB > directory mean : > > -"nodes.dat" : Is that the node table, which contains the NodeID and the > belonging RDF term? Its part of the node table: NodeId->bytes/string for the Node The other part is node2id. > > -What's the purpose of the "node2id.idn/.dat" and why does almost every > file has a .dat and .idn version of it ? .idn : the B+Tree branch nodes. .dat : the B+Tree data nodes. These two have different formats. > -Is it possbile to open these files in a readable way ? Is it possbile > to view those files? No. They are binary. The layout in in the code. (jena-cmds has "tdb.tools.dumpbpt" -- it might still work.) > I'm currently doing research on distributing those indexes on several > machines and therefore want to fully understand their purpose and > interactions. If you could therefore recommend me some helpful > resources, literature etc. like the "Clustered TDB: A Clustered Triple > Store for Jena"-paper I would be very thankful. Thank you for your > patience! First step - is distributing the indexes the best way to scale a triple store? I'm not convinced it is the only choice. We have Claude looking at using Cassandra for RDF storage. https://github.com/Claudenw/jena-on-cassandra We have Dick contributing a https://github.com/apache/jena/pull/233 https://github.com/dick-twocows/jena (Dick - sorry - haven't caught up on this yet - the holiday in Provance was wonderful) Implementing on Apache Spark if the busienss case is for analytic queries of the bug data style and scale. See also BlazeGraph which IIRC has some form of distributed B-Tree. TDB B+Trees are not special so a google search for "distributed B-tree" is useful e.g. maybe http://www.vldb.org/pvldb/1/1453922.pdf https://www.usenix.org/system/files/conference/atc16/atc16_paper-mitchell.pdf See also 4Store. See also TDB2 ... github.com/afs/Mantis TDB2 is a derived TDB where the B+Trees are copy-on-write which makes the transaction journal only contain a few byutes for each commit. TDB1 is a forward log - the changed blocks go into the journal so it can get a bit big. And lots of other engineering changes. > > > Regards > > Dennis Grinwald > > > > > > On 24.05.2017 01:53, Andy Seaborne wrote: > On 24/05/17 02:33, Dennis Grinwald wrote: > > Hi there, > > Hi Dennis, > > > I'm very new to the Jena TDB and have several questions about it's > > Architecture. I would be very thankful if you could answer the > following : > > All Nodes get given a NodeId which is a fixed length 8 byte sequence. > > Some Nodes (RDF Terms) like integers, dateTimes, hold the value in the > NodeId itself (8 bits types, 56 bits of value) otherwise the NodeId > records the location in the node table for the details of the node are > recorded (URIs, strings, out of range integers...). > > == Lookup NodeId -> Node > > The NodeId is the location in the node table so TDB just fetechs it from > the file. > > There is a large cache as well. This lookup happens on query results so > it is important. > > == Lookup Node -> NodeId > > For this, the Node is hashed (MD5 : 128 bits) and the hash assumed to be > unique. 128 bits is a very large number! > > There is then a B+Tree with key node hash and value NodeId. > > This lookup happens when building the query. It's cached and there is a > a "miss" cache as well for nodes not in the database. > > == SPO etc > > The key is 3 NodeIds - 24 bytes. There is no value part. > > Because the B+Tree has the keys sorted, you can do lookup of S?? to find > the start of all triples with that S (lookup S00), then a range scan > forwards until (S+1)00 through the B+Tree leaves. The leaves are > chained horizontally. (This is for TDB1 ; not true in TDB2 - the leaves > are not linked.) > > Similarly, you can lookup SP?, or SPO. > > The B+Trees are about order 200 - they use a 8Kbyte block. > >> >> 1. In "Clustered TDB: A Clustered Triple Store for Jena" published by >> Mr. Seaborn, Owens, Gibbins and Schraefel, it says that the Indexes: >> SPO, POS, OSP are B+-Trees. My question is: How are the internal nodes >> (keys) of this B+-Tree represented and what are the values/value >> pointers in the leaves of the B+-Tree? > > That was using a much older version of TDB but the design is the roughly > the same. > >> 2. On "http://jena.apache.org/documentation/tdb/architecture.html"; it >> says, that the Node to NodeID mapping is realized by a B+-Tree. My >> question as in "1." : How are the internal nodes (keys) of this >> B+-Tree represented and what are the values/value pointers in the >> leaves of the B+-Tree? > > That lookup does not need the sorted property of B+Trees, just a a > key->value lookup such as a external hash index. But the cache is so > important anyway, it was simpler to have one datastructure. > > It is quite important in TDB that it uses it's own implementation of > B+Trees because they are efficient (in space and time) for the TDB > case. A general purpose B+Tree storage package is doing a lot of things > that TDB does not need (e.g reading and writing the bytes of keys > without copies for safety). Transactions need to be coordinated across > multiple B+Trees so a transactional B+Tree would not be much help unless > it had a way to integrate into a larger transaction system. > > Normally, the B+trees are memory-mapped into the JVM which gives the > caching, using in effect, the OS disk cache. > > Hope this description helps, > > Andy > > > > Thank you for your time. > > > Best regards > > Dennis Grinwald > >
