Title: What is fanout in R-Tree?
Tags: database;tree;r-tree
Question: I have a doubt about R-Tree data structure. What is fan-out in R-Tree. Is it a Maximum number of entries?

How can we determine the minimum and maximum number of entries in R-Tree? Let say if i have 10000 points and my page size i 8kb.

Thanks

Comment: Are you sure you mean R-tree and not B-tree (or B+-tree)?

Comment: Note that fanout determined by page size only makes sense for external trees, that is ones that are stored in files and too large to be fully loaded in memory. In memory, trees with low fanout are more efficient, because they need fewer comparisons per search in total.

Comment: yup i am sure it's R-tree.

Here is the accepted answer: Fan-out, in any tree, is number of pointers to child nodes in a node.

Different trees have different fan-out.

A binary tree has fanout 2.

A B-tree has a fan-out B, with all nodes except leaves having between B/2 and B children. External (on-disk) implementation often relax the minimal number of children restriction to save some updates.

In databases, B-trees or their variant called B+-trees is often used so that each node has size of 1 page and the fan out determined by number of sort keys and pointers that fit in that space.

An R-tree is a search tree where indices are multi-dimensional intervals. These may possibly overlap. It may have any fan-out. Usual is number of 2 to number of dimensions (so 4 for 2-dimensional, 8 for 3-dimensional etc.). But it may have higher fanout too and organizing it similar to B-tree is certainly possible.

```
  How can we determine the minimum and maximum number of entries in R-Tree? Let say if I have 10000 points and my page size is 8KiB.
```

The size of the tree node does not have to match page size. If it does (usually used for external, i.e. on disk, implementations), you still need to know how large the sort key is and how large the pointer is. An R-tree needs 2 coordinate values, minimum and maximum, per dimension. So a 2-dimensional R-tree with double precision coordinates (the common case appearing in mapping applications) will have four 64 bit values describing the rectangle plus a child pointer, for which an external implementation probably wants to use 64 bits as well. That is 20 B per child and you can squeeze 409 of these in an 8 KiB page. The number of points does not matter. Dimension and precision of coordinate system does.

In memory, trees with low fanout are more efficient, because though they are deeper, they need fewer comparisons per search. However on disk (in databases) the slow operation is reading and since that can only be done in blocks, it is faster to reduce number of nodes by having each node fill whole block and have correspondingly higher fanout.

Comment for this answer: I disagree with the last paragraph. Even in memory it may be beneficial to have larger fanout, because of L1/L2/L3 caching etc. - for the same reason that insertion sort is faster than heapsort on small arrays.

Here is another answer: "Fanout" refers to the number of pointers per node which R-Tree is having

Comment for this answer: @user3030823: No. It means number of entries _per parent node_.
Comment for this answer: does it mean number of entries?

{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 2, 'CommentCount': 3, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2014:00:03/05/14', 'FavoriteCount': 2.0, 'PostTypeId': 1, 'Tags': '<database><tree><r-tree>', 'Title': 'What is fanout in R-Tree?', 'ViewCount': 9593, 'id': 22190885, 'user_AboutMe': None, 'user_AccountId': 3635637.0, 'user_DisplayName': 'user3030823', 'user_Reputation': 97.0, 'user_Views': 27.0, 'user_id': 3030823.0}}