OSDev.org

alexfru wrote: Within a node, keys and their respective values are logically tied/paired. You can have an array of k-v pairs in a node. Or you can have it split into two distinct arrays, an array of keys and an array of values, still directly corresponding to one another.
Obviously, if you want quick key search (which is the hole point of the data structure at hand), you keep the array of keys ordered/sorted. So, when you insert a new key between, let's say, key3 and key4 (because key3 < new key < key 4), you also insert its corresponding value between value3 and value4 (irrespective of how values relate to one another). The new key and its value both have the same index in separate arrays or in the same array, the index that used to belong to key4-value4 pair. key4-value4 moves one place.

The same ordering logic applies to links to children as those links are stuck between adjacent keys and there are two extra links on the sides.

I'm sorry, I'm having trouble understanding what it is that you don't understand.

Wikipedia wrote:...where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements. Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.

typedef struct _node2 {
	data_t 	data;			// Some hypothetical data
	node* 	children[2];	// Two child links 
} node2_t;					  // 2-node

typedef struct _node3 {
	data_t	data[2];		 // Two data elements
	node*	children[3];	 // Three child links
} node3_t;					  // 3-node

typedef struct _leaf1 {
	data_t	data;			
} leaf1_t;					  // Leaf with one data element 

typedef struct _leaf2 {
	data_t	data[2];			
} leaf2_t;					  // Leaf with two data element 

physecfed wrote:

alexfru wrote: Within a node, keys and their respective values are logically tied/paired. You can have an array of k-v pairs in a node. Or you can have it split into two distinct arrays, an array of keys and an array of values, still directly corresponding to one another.
Obviously, if you want quick key search (which is the hole point of the data structure at hand), you keep the array of keys ordered/sorted. So, when you insert a new key between, let's say, key3 and key4 (because key3 < new key < key 4), you also insert its corresponding value between value3 and value4 (irrespective of how values relate to one another). The new key and its value both have the same index in separate arrays or in the same array, the index that used to belong to key4-value4 pair. key4-value4 moves one place.

The same ordering logic applies to links to children as those links are stuck between adjacent keys and there are two extra links on the sides.

I'm sorry, I'm having trouble understanding what it is that you don't understand.

When I first sat down to write a response, I confused myself. That, combined with the fact that I'm using iffy terminology at best, should show you the grip I have on the subject. It might stem from the fact that I'm trying to think of B-trees in terms of linked lists, a data structure I understand well enough. So, let's reapproach this.

physecfed wrote:I'm looking at the Wikipedia article for a 2-3 tree. It says,

Wikipedia wrote:...where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements. Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.

So, it sounds like this is a general representation of the following nodes/leaves (some of the syntax is pseudocodish, I wrote it quickly to see if I was getting the point):

Code: Select all

typedef struct _node2 {
	data_t 	data;			// Some hypothetical data
	node* 	children[2];	// Two child links 
} node2_t;					  // 2-node

typedef struct _node3 {
	data_t	data[2];		 // Two data elements
	node*	children[3];	 // Three child links
} node3_t;					  // 3-node

typedef struct _leaf1 {
	data_t	data;			
} leaf1_t;					  // Leaf with one data element 

typedef struct _leaf2 {
	data_t	data[2];			
} leaf2_t;					  // Leaf with two data element 

physecfed wrote:So, what does "self-balancing" refer to? To me, it sounds like the processes of altering the tree perform balancing in order to assure that the search and accesses on the tree take place quickly - it sounds like trading speed of modification for speed of access.

physecfed wrote:As to the key-value stuff, is this as simple as exchanging the hypothetical "data_t" element in the above representation to say, char* key and char* value?

physecfed wrote:I suppose what is tripping me up now is the determination of where keys go in the tree.

physecfed wrote:The Wikipedia article's section on insertion talks about searching for the proper insertion point for the key - what determines where an arbitrary key goes when inserted into the tree?

alexfru wrote:A question out of the blue. Are we done with the previous stuff and moving on to other things?
There isn't much "self-balancing", not in the sense of a tree magically rebalancing itself or maintaining the balance having a cost of zero. Certainly, there are additional tree manipulations for this. If you've read about 2-3/2-3-4/red-black/AVL/etc trees, there are rotation operations that are done to make sure that the distances from every leaf node to the root are about the same. B trees are very similar.

physecfed wrote:I know enough about trees so far (however little, granted) to understand somewhat shakily that "not all binary trees are B-trees"; that B-trees are a subset of binary trees that meet certain conditions. The book contains a tree implementation where the data value contained is an int, with two pointers called left and right. It appears that where the node is inserted is based upon the new value compared to the old, where values less than the parent are inserted as the left child, and values greater are inserted to the right. Where does that stand with relationship to a B-tree (that is, what are the criteria that must be met for a binary tree to be a B-tree? I understand there's different types of B-trees).

I see that Wikipedia wrote:The B-tree is a generalization of a binary search tree in that a node can have more than two children

gerryg400 wrote:

physecfed wrote:I know enough about trees so far (however little, granted) to understand somewhat shakily that "not all binary trees are B-trees"; that B-trees are a subset of binary trees that meet certain conditions. The book contains a tree implementation where the data value contained is an int, with two pointers called left and right. It appears that where the node is inserted is based upon the new value compared to the old, where values less than the parent are inserted as the left child, and values greater are inserted to the right. Where does that stand with relationship to a B-tree (that is, what are the criteria that must be met for a binary tree to be a B-tree? I understand there's different types of B-trees).

You need to begin by understanding that B-trees are not a type of binary tree and binary trees are not a type of B-tree. They are entirely different. If a B-tree were constructed with only 1 inner node per node it might be arguably described as a binary tree but I would then argue that it is no longer a B-tree.

I see that Wikipedia wrote:The B-tree is a generalization of a binary search tree in that a node can have more than two children

What this is saying is that a B-Tree is a tree. (Not a binary tree). However it misses the major feature of a B-Tree. Not only do the nodes have potentially more than 2 children B-tree nodes contain potentially more than one inner node. The size of the nodes is chosen to maximise performance.

Schol-R-LEA wrote:There is an excellent, if quite dated, book called File Structures which discusses data structures for organizing and traversing information in secondary storage. It covers B-Trees and B+-Trees in depth, along with hash tables and tries, mainly from application perspective but still applicable to file system design (indeed, you would need to understand how it works in general use before you can realistically hope to use it in FS implementation).

Gerry is (mostly) right: discussing B-Trees in terms of binary trees is a Bad Idea, even if some discussion of binary trees is unavoidable as groundwork. While the B-Tree can in some ways be seen as a generalization of a balanced binary tree, and is often presented in that way due to persistent confusion on the subject, that view is very misleading - they are very different in structure, purpose, and dynamic behavior. They are related, especially historically, so comparing them isn't apples-to-oranges, but it is more like apples-to-apple-orchards. You need to understand binary trees before you can understand B-Trees, but saying that a B-Tree is a binary tree is like saying an aircraft carrier is the same thing as a log canoe.

From a practical standpoint, the main difference is that binary trees are used for organizing and traversing data nodes in memory, while B-Trees and their derivatives are mainly for use sorting and searching keys related to data in some sort of secondary medium with a significantly longer access time than memory (disk, CD, mag tape, some kinds of flash memory, etc.). Whereas a balanced binary tree (which includes red-black trees, AVL trees, splay trees, etc.) is meant to reduce the number of nodes traversed while searching, the B-Tree also has to reduce the number of reads from and writes to mass storage, which on modern machines can be several orders of magnitude slower than primary store (milliseconds or even seconds, versus nanoseconds). You wouldn't use a B-Tree for data in memory, as it would be slower on average than a more basic form of balanced tree, and more cumbersome; conversely, using a general binary tree for traversing nodes in secondary storage would require so many disk reads that the advantages of a tree over a list would be irrelevant, since the access time for the disk would dominate the operation.

The salient point is that not only is the data in secondary storage, usually so are at least some of the keys as well. The tree itself can be part in and part out of main memory, so in order to traverse the B-Tree, you need to read from secondary storage, usually more than once. Being able to do so efficiently is an important property of B-Trees and their ilk, as it allows you to work on structures where not only the is data too large to fit in memory, the index to the data is as well, so caching the whole index isn't an option. This is important in a large database, but it has obvious implications for file system structures as well (it could even be applied to paging schedulers, I think, though I've never heard of it being done).

iansjack wrote:In addition, you want to make the tree as balanced as possible, so that each node at a given level has roughly the same number of subnodes.

typedef struct node {
    datatype_t d1, d2;
    struct node* a;
    struct node* b;
    struct node* c;
} node_t;