Stack Overflow
Stack Overflow

Questions tagged [b-tree]

B-trees are a type of self balancing search tree where each node can hold multiple keys and all leaf nodes are the same distance from the root.

B-trees are an extension of self-balancing binary search trees to allow each node to hold multiple keys and have multiple children. They are designed to take advantage of systems that can read and write in large blocks, and are commonly used in databases and file systems.

B-trees on Wikipedia

762 questions
160
votes
8 answers

B-Tree vs Hash Table

In MySQL, an index type is a b-tree, and access an element in a b-tree is in logarithmic amortized time O(log(n)). On the other hand, accessing an element in a hash table is in O(1). Why is a hash table not used instead of a b-tree in order to…
JohnJohnGa
  • 15,446
  • 19
  • 62
  • 87
88
votes
4 answers

When to choose RB tree, B-Tree or AVL tree?

As a programmer when should I consider using a RB tree, B- tree or an AVL tree? What are the key points that needs to be considered before deciding on the choice? Can someone please explain with a scenario for each tree structure why it is chosen…
Palladin
  • 983
  • 1
  • 7
  • 10
50
votes
2 answers

Red Black Tree versus B Tree

I have a project in which I have to achieve fast search, insert and delete operations on data ranging from megabytes to terabytes. I had been studying data structures of late and analyzing them. Being specific, I want to introduce 3 cases and ask…
swanar
  • 635
  • 1
  • 6
  • 10
49
votes
10 answers

AVL tree vs. B-tree

How is an AVL tree different from a B-tree?
neuromancer
  • 53,769
  • 78
  • 166
  • 223
48
votes
2 answers

B trees vs binary trees

If I am implementing in-memory(RAM) search operation with b trees, then would it be better in terms of caching or some other effects when compared with binary trees? What I know is- binary search tress---O(log n) btrees ---------------O(c log…
user609306
  • 1,333
  • 6
  • 17
  • 27
34
votes
6 answers

What is a good open source B-tree implementation in C?

I am looking for a lean and well constructed open source implementation of a B-tree library written in C. It needs to be under a non-GPL license so that it can be used in a commercial application. Ideally, this library supports the B-tree index to…
Tall Jeff
  • 9,834
  • 7
  • 44
  • 61
34
votes
5 answers

Advantage of BTREE?

I create indexes without the USING BTREE clause. Is there any advantage of using BTREE index? CREATE INDEX `SomeName` USING BTREE ON `tbl_Name`(`column_name`);
shantanuo
  • 31,689
  • 78
  • 245
  • 403
32
votes
1 answer

How to lay out B-Tree data on disk?

I know how a B-Tree works in-memory, it's easy enough to implement. However, I don't know how to find a data layout that works effectively on disk, such that: The number of entries in the B-Tree can grow indefinitely (or at least to >…
Martin Häusler
  • 6,544
  • 8
  • 39
  • 66
32
votes
3 answers

Postgres usage of btree indexes vs MySQL B+trees

We are in the process of migrating from MySQL to PGSQL and we have a 100 million row table. When I was trying to ascertain how much space both systems use, I found much less difference for tables, but found huge differences for indexes. MySQL…
Greedy Coder
  • 1,256
  • 1
  • 15
  • 36
29
votes
5 answers

Why is it important to delete files in-order to remove them faster?

Some time ago I learned that rsync deletes files much faster that many other tools. A few days ago I came across this wonderful answer on Serverfault which explains why rsync is so good at deleting files. Quotation from that answer: I revisited…
ovgolovin
  • 13,063
  • 6
  • 47
  • 78
28
votes
7 answers

Looking for a disk-based B+ tree implementation in C++ or C

I am looking for a lightweight open source paging B+ tree implementation that uses a disk file for storing the tree. So far I have found only memory-based implementations, or something that has dependency on QT (?!) and does not even compile. Modern…
Laurynas Biveinis
  • 10,547
  • 4
  • 53
  • 66
27
votes
5 answers

Does anybody know how B-Tree got its name?

I'm reading CLRS and studying the B-Tree now. CLRS claims that B-Tree naming is not clear yet: [Bayer, McCreight, 1972] doesn't offer the reason why B-Tree is named "B-Tree". I haven't investigated this issue any further... but does anyone know the…
user273210
26
votes
4 answers

Existing implementation of Btree or B+tree in Java

I am doing a project in which I require btree or b+tree data structure. Does anyone know of an existing implementation of btree or b+tree (with insert, delete, search algorithms)? It should accept string as input and form btree or b+tree of these…
rohit
  • 423
  • 1
  • 6
  • 12
26
votes
2 answers

Advantage of B+ trees over BSTs?

I'm learning about B+ trees in a class about databases and I was wondering what concrete advantages B+ trees would give over Binary Search Trees? It seems like they both have O(logN) average complexity for most operations of note but B+ trees also…
riggspc
  • 612
  • 3
  • 7
  • 15
23
votes
5 answers

In what order should you insert a set of known keys into a B-Tree to get minimal height?

Given a fixed number of keys or values(stored either in array or in some data structure) and order of b-tree, can we determine the sequence of inserting keys that would generate a space efficient b-tree. To illustrate, consider b-tree of order 3.…
nbbk
  • 1,102
  • 2
  • 14
  • 32
1
2 3
…
50 51