AVL tree vs. B-tree
How is an AVL tree different from a B-tree? ...
b-tree
Paged binary trees vs. AVL trees and/or B-trees
How are paged binary trees different from AVL trees and/or B-trees? ...
recombination in B-trees
When does recombination happen upon deletion in B-trees? Can you show a simple example? Is it the same for B+ trees? ...
Secondary keys in a B-tree
Let's say that there is a file that contains an unsorted list of student information, which includes a student ID number as well as other information. I want to make a program that retrieves student information based on student ID number. In order to make it efficient, I store the student IDs in a B-tree. So when I enter a student ID ...
How to traverse a Btree?
I have a Btree and I'm trying to figure out how traverse it so that the keys are displayed ascending order. All I can figure out is that this can be done with a recursive function. What's the pseudo-code to do it? ...
Preoder traversal of a Btree
I'm trying to figure out how to do a preorder traversal of a Btree. I know that generally preorder traversal works like this: preorder(node) { print value in node preorder(left child) preorder(right child) } What's confusing to me is how to make this work with a Btree, since in each node there are multiple values and multiple child p...
Help with Btree homework
I need to do a preorder traversal of a Btree, and among other things, print the following information for each page (which is the same thing as a node): The B-Tree page number The value of each B-Tree page pointer (e.g., address, byte offset, RRN). My questions are: 1. How do you figure out the byte offset? What is it offset from? 2....
Databases and B+Trees indexes
Where can I find information on whether which databases are using B+Trees over B-Trees for their index implementations? Oracle appears to be using B+Trees. Although they don't describe it on their documentation, their graphics appear to be pointing that B+Trees are actually being used. ...
Berkeley DB java edition, any LGPL or BSD alternatives in Java?
Hi All, I am dealing with a huge dataset consisting of key-value pairs. The queries are always in the form of range queries on the key space (keys are numbers) hence any persistent B-Tree like structure will handle the situation. I would like to use BDB-Java Edition but the product is closed source and my company doesn't want to buy BDB...
What is the way to maintain database indexes in files
I'm writting key-value storage for milions of documents - for study and fun. I added default b-tree indexing on key but of course there is no way to load all indexes to memory. For now storage have two types of files data (not ordered key-value records) and index (no efficient conception for search, adding and deleting). In b-tree obje...
Indexing count of buckets
So, here is my little problem. Let's say I have a list of buckets a0 ... an which respectively contain L <= c0 ... cn < H items. I can decide of the L and H limits. I could even update them dynamically, though I don't think it would help much. The order of the buckets matter. I can't go and swap them around. Now, I'd like to index the...
Sequentially Constructing Full B-Trees
If I have a sorted set of data, which I want to store on disk in a way that is optimal for both reading sequentially and doing random lookups on, it seems that a B-Tree (or one of the variants is a good choice ... presuming this data-set does not all fit in RAM). The question is can a full B-Tree be constructed from a sorted set of data...
B-Tree - I don't get the "minimal degree" thing
I'm trying to implement a B-Tree according to the chapter "B-Trees" in "Introduction To Algorithms"... what I don't quite get is the "minimal degree"... it says it's a number which expresses the lower/upper bound for the number of keys a node can hold. It it further says that: every non-root node stores at least t-1 keys and has t chil...
How can I use imply an OR query on an B-Tree?
I want to use b-tree for index, but I can't think out an solution for OR query. For OR query, I mean something like select * from table where id between 1 and 5 OR id between 10 and 15; if I use id as the key in the b-tree, than how can I do query like above on the b-tree? when search through the b-tree, assume that the key that are s...
How multiple column b-tree index is organized
I want to understand better index organization. Imagine we have a table with 2 columns: CREATE TABLE user( name varchar(100) ,age int) We would like to create an index: CREATE INDEX IDX_MultiColIdx on user(name,age) How would B-Tree index organization look like? In case of one column, say, age, the organization is clear: eve...
Dumping unreferenced pages in an sqlite file and re-referencing them.
Hi there! I got a damaged sqlite3 file with some pages referenced twice and some with zero references. I would like to know and dump these unreferenced pages and, if possible, manually re-reference them. The result of PRAGMA integrity_check; follows: "*** in database main *** On tree page 108 cell 0: 2nd reference to page 247 On tree p...
Is there a B-Tree Database or framework in Python?
I heard that B-Tree datbases are faster than Hash tables, so I thought of using a B-Tree Db for my project. Is there any existing framework in python which allows us to use such Data structure or will I have to code from scratch? ...
What Tree structure should I use for indexing?
I'm thinking of experimenting with using a tree-structure for indexing as I want to test whether it is faster than my current indexing implementation which is in essence a hash based lookup. I've read up on various questions and articles about performance of B-Trees, AVL-Trees and Red-Black Trees and can't really see much difference bet...
How Balanced are balanced B-Trees
Say I have a B-Tree with nodes in a 3-4 configuration (3 elements and 4 pointers). Assuming I build up my tree legally according to the rules, is it possible for me to reach a situation where there are two nodes in a layer and one node has 4 exiting pointers and the other has only two exiting pointers? In general, what guarantees do I ...
B-tree: How many keys are left in root node??
add the following keys to a B-tree, the provided order is : 18, 44, 63, 5, 3, 7, 46, 38, 22, 37. The oder of B-tree is 4. Q: How many keys are left in root node? I thought it was 1, because the order = 4... but it is wrong!! ...