BIG data

How many web pages are there in the world?  (Do a quick check to get an estimate.)
How many:__________________

Imagine that Google has the web pages all stored in a database.

A binary search tree (that is relatively balanced)  has O(lg2(N)) search time.
	   N=1         N=3                                   N=7 					     N=15

To find an item in a tree of size 1 requires 1 look.
To find an item in a tree of size 3 requires 2 looks, one for each level.  
To find an item in a tree of size 7 requires 3 looks.
A tree of size 1023 requires 10 looks.
A tree of size N requires LG(N) (log base 2 of N) looks.

How many levels of a binary search tree would be needed for all the Web pages in the world?
How many:__________________

That is too big to fit into main memory, and that many disk accesses for each search would be very time consuming. What can we do?

A traditional binary search tree has a data item, and a left and right link.
Each child is (recursively) a binary tree.

You can obviously do a binary search.
At each level, assuming the tree is fairly balanced, the number of possibilities left is cut in half.

To find an item in a tree of size 1 requires 1 look.
To find an item in a tree of size 3 requires 2 looks, one for each level.  
To find an item in a tree of size 7 requires 3 looks.
To find an item in a tree of size 15 requires 4 looks.
A tree of size 1023 requires 10 looks.
A tree of size N requires LG(N) (log base 2 of N) looks.

Pretty good, until you get into fairly large samples.
Size 1023, for example, if it requires 10 DISK ACCESSES, is fairly slow.

But there is no law saying we can only have one item in each record.
What is we had THREE items (with four links) instead of 1?

But there is no law saying we can only have one item in each record.
What is we had THREE items (with four links) instead of 1?

It would be like we lumped together the root, left child, and right child of a binary tree.
That way in ONE level we would go the equivalent of TWO levels in the binary tree.

In TWO levels, it would be the equivalent of 4 levels of binary tree.
And that would mean only 2 DISK accesses, instead of 4 for a binary tree.

But why stop there?
Could we do SEVEN(7) items in a node?

But why stop there?
Could we do SEVEN(7) items in a node?

Each level would replace THREE levels in a binary tree.
So there would only be 1/3 as many disk accesses, in a large database.

How big can we go?

Assume we have SSN as an identifier.
(9 digits, at most 9 bytes.)
Assume each pointer takes 32 bits, 4 bytes.

If a node contains 7 items, it would take 7*9+8*4 bytes,  95 bytes.
But even small computers today have disk sectors of at LEAST 4096 bytes.

How many items could we fit in a 4096 byte disk block?
(rough estimate, 4096/(8*(4+9)) bytes)

It would be easy for such a tree to have enough bytes to replace FIVE levels of a binary tree.
This would mean there would be 1/5 of the disk accesses of a binary search tree, for a large database.

If there were 8192 bytes in a disk block, how many SSNs could we fit into a node?

_________________
But this kind of data structure is a bit harder to program.
This algorithm is similar to the B and B+ algorithm mentioned in the book.

RULES:
Assuming there are N items per node, there are N+1 pointers.
All nodes, except possibly the leaf node, are at least half full.
All data records are at the bottom (leaf) level.
The tree (tree-ish structure) is always perfectly balanced.

To start:
Insert in the root node (insertion sort) until it is full.
When you add one more node, the root node gets split.
Pick the middle item of the N+1 items.  
	Items less than it get put on one node.
	Items greater than it get put in another node.
	The middle item is promoted (up) and inserted in a new root node.
	The two new records are children of the new root node.

Insertion in the general case:
	Start at the root node.
	Based on the items in the node, go downward, until the appropriate link is NULL.
	Make a new data record and insert the item in the (internal) node.
	If that would make the node too full:
		Look to the next node to the left.
		If there is room in that node, rotate the lowest item in this node over to the lower node.
		If not, look to the next node to the right.
		If there is room in that node, rotate the highest item in this node over to the higher node.
		If there is not room in this node or either neighbor node:
			Pick the middle item of the N+1 items.  
			Items less than it get put on one node.
			Items greater than it get put in another node.
			The middle item is promoted (up) and inserted in the parent node.
			If that makes the parent node too full,
				check left neighbor, then right neighbor, then split and promote.
			If you reach the root node and split it, 
				at that moment every node in the tree goes down one level, 
				but the tree is still balanced.
Deletion in the general case:
		Follow the pointers down until you find the leaf.
		If the leaf is the item, return the pointer to the data record, 
			replace pointer to the data record with NULL.
		If an item has a NULL pointer on both sides, you may delete that item,
			replacing two NULL pointers and a partition item by a single NULL pointer,
			reducing number of items in that node by one.
		Do not delete the ROOT node.			

Assume you have a tree with 3 items (4 pointers) in each node.
(1/3 full is too small; 2/3 or 3/3 if fine.)

a. Insert the alphabet in order and diagram the tree every time a node is split.

b. Insert the alphabet in reverse order and diagram the tree every time a node is split.

c. Insert the alphabet in the following order and diagram the tree every time a node is split.
M F R C I P U B E H K O T X A D G J L N Q S V S Y Z

If in small groups, each person does a different order, and then compare in group.