Stack Overflow
Stack Overflow

Questions tagged [b-plus-tree]

A B+ tree is an n-ary tree with a variable but often large number of children per node, suitable for storing data for efficient retrieval in a block-oriented storage context. B+ trees are often used in file systems and databases.

A B+ tree is an n-ary tree with a variable but often large number of children per node, suitable for storing data for efficient retrieval in a block-oriented storage context. B+ trees are often used in file systems and databases.

https://en.wikipedia.org/wiki/B+_tree

27 questions
4
votes
1 answer

Is this B+ Tree Valid?

In a B+ tree, can a non leaf node exist such that it's key value is deleted? What this means is that the B+ tree has a value in its intermediate non leaf node but not in any of its leaf nodes. Consider the following structure. I came across this…
Crystal Meth
  • 589
  • 1
  • 4
  • 16
3
votes
1 answer

Why we are not saving the parent pointer in "B+ Tree" for easy upward traversal in tree?

Will it affect much if I add a pointer to the parent Node to get simplicity during splitting and insertion process? General Node would then look something like this : class BPTreeNode{ bool leaf; BPTreeNode *next; BPTreeNode *parent;…
Nitesh Kumar Tiwari
  • 33
  • 3
2
votes
1 answer

CSharpTest.Net.Collections.BPlusTree RecentCache bug?

I've been using this implementation of B Plus Tree for some time. I've noticed that the 'Recent' cache is buggy. Here's how the bug is produced: I add some KVPs, and commit the tree. I add some more KVPs and rollback the tree. I add some more KVPs…
Usman Shahid
  • 101
  • 2
  • 5
1
vote
1 answer

Bulk Loading B+ trees: Top-down and Bottom-up approach

I know there exists a technique to bulk load sorted data in a B+ tree. However, I read at some places that there are 2 ways how bulk-loading can be approached - top-down and bottom-up. Resource (1) mentions that in the top-down approach, most of the…
Saasha Joshi
  • 11
  • 1
  • 6
1
vote
1 answer

How to store array index (an integer) as keys in a B+tree?

I have looked at every example of a B+tree in JavaScript on GitHub, and have tried simplifying one down to semi-readable code from this. But I still don't understand what the structure of the keys array is for each internal node. What do the keys…
Lance
  • 75,200
  • 93
  • 289
  • 503
1
vote
1 answer

Is this a bug in Database System Concepts 6th edition-Figure 11.11 Querying a B+-tree.-procedure printAll(value V)?

In Database System Concepts, 6th edition, chapter 11, in "Figure 11.11 Querying a B+-tree.", there is a procedure printAll(value V). It is used to print all records with search key value V (there can be duplicates). It calls find(V), which returns…
Jason Law
  • 965
  • 1
  • 9
  • 21
1
vote
1 answer

Will key in the index be removed after deletion in B Plus tree?

I'm a little confused with the deletion in B+ tree. I searched a lot in Google and find that there are two implementation when the key you want to delete appears in the index: Delete the key in the index Keep the key in the index Algorithm from…
Ynjxsjmh
  • 28,441
  • 6
  • 34
  • 52
1
vote
1 answer

Can B+tree search perform better than Binary Search Tree search where all keys-data of the leaf nodes are in the memory?

Assume that we are implementing a B+ tree in memory, keys are at the internal nodes and key-data pairs are in the leaf nodes. If B+tree with a fan-out f, this means that B+ tree will have a height of log_f N where N is the number of keys, whereas…
burcak
  • 1,009
  • 10
  • 34
1
vote
2 answers

Protobuf-net asking for TypeModel.CS when used with Generics for deserialization

I have billions of objects that I'm trying to structure them in a B+Tree serialized to HDD. I'm using BPlusTree library for the data structure and protobuf-net for serialization/deserialization. In this regard I define my classes as: …
Dr. Strangelove
  • 2,725
  • 3
  • 34
  • 61
1
vote
1 answer

Fast Random file access in java

I have built a data structure somewhat similar to a non clustered B+ tree index(on a field say K), over a data file with file offsets as my leaf node values. Now for any lookup, I need to read from a random point on the file. As I understand , most…
ping localhost
  • 479
  • 3
  • 22
1
vote
0 answers

BPlusTree crabbing latches performance

I was developing an in-memory version of B+Tree with crabbing technique (you have to obtain lock of child before releasing lock on parent). My target language of implementation is C# in my implementation I have a backing Dictionary, for…
Egor
  • 175
  • 8
0
votes
1 answer

Should data in B+Tree be ordered and how much data should I be loading at a time?

Within my B+Tree I have ordered keys at the leaf levels, with data pointers to a separate data file. This question refers to the order of data within this data file. As I see it, When ordered: It's Easier to load all the data in a block when one is…
roat
  • 73
  • 5
0
votes
0 answers

Calculating B+ tree memory usage (minimum, maximum)

I have a B+ tree index containing 10M leaves. I know that a block size in the memory is 4KB, and that RAM is also 4KB. How can I calculate what is the maximum and minimum memory usage? also, how can I tell what is the actual storage space allocated…
user16425284
  • 19
  • 1
0
votes
1 answer

The problem of designing, inserting and deleting of the B+ tree values

I have the question regarding my homework: 1) First of all, assuming that 4 pointers might fit in an internal node and each leaf node can store 4 key values, the B+ tree should be constructed with the following values: 2, 3, 5, 7, 11, 17, 19, 23,…
Ulvi Bajarani
  • 13
  • 9
0
votes
0 answers

C++: data loss in B+ tree insertion

Whenever I insert a new element in my B+ tree, it seemingly rewrites each data point with the one to be inserted, before the insert function even starts. The only possible cause I've found is that my bPLus object doesn't seem to have access to the…
John Smith
  • 1
1
2