TTree Fetch time complexity

ROOT
1

Hello everyone,

              I have a question in my mind. TTrees physically store data in TBuffers which are character array? Am I right in interpreting? If I store my data physically in BTree layout I know the time complexity to fetch is log(n). But in case of TTree can I mathematically formulate its time complexity? I need some guidance in this respect!!
2

Hi,

ROOT TTrees are conceptually different than binary trees. A TTree can be seen as a table with N entries and k columns.

In a binary tree, the complexity of a search is a function of the number of elements of the tree, since you need to start from the root node and go down the tree to find the element you want. This is not the case for a TTree.

When trying to get an entry of a TTree, for every column (a.k.a. TBranch), ROOT calculates the offset in which that entry is and then retrieves it from the right buffer (possibly reading from disk first).

Cheers,

Enric

3

Getentry command does the fetching…Right? So if I want to mathematically express its complexity then how do I express it? Is it O(1) then?

4

Hi,

Yes in first approximation GetEntry is O(1) [There is many nuances though as reading some entries might take a bit longer than other depending on whether they are triggering a TTreeCache read and/or decompression]

Cheers,
Philippe.