/*********************************************************************** Bplus tree by Kevin Jenkins Follows the normal algorithm for a B+ tree from class with the following changes 1. Each page has a next pointer that points to the next node at the same level This is used for sequential search (2). 2. The Leaf Print command prints out all the leaves using the next pointer of each page 3. The KeyType field of the template is for the numeric type of the key (int, float, etc.) The DataType field of the template is for the associated key value, which must be a type with the = operator defined or overloaded properly 4. The order of the tree must be passed to the constructor, no arbitrary limit other than the range of an int 5. Nested memory management is handled through constructors and destructors, instead of explict function calls ***********************************************************************/ #ifndef B_TREE_CPP #define B_TREE_CPP #include "iostream.h" #include "process.h" #include "ctype.h" template struct Page; template struct Item { Item(); ~Item(); Item& operator = (const Item& right_op) { if (this != &right_op) { key=right_op.key; right=right_op.right; *data=*(right_op.data); } return *this; } KeyType key; Page *right; DataType *data; private: // Dont allow the copy constructor Item(const Item&); }; template Item::Item() { data = new DataType; right=0; key=0; } template Item::~Item() { delete data; data=0; } template struct Page { Page (int itemCount) {size=0; next=0; items=new Item[itemCount*2];} ~Page() {size=0; delete [] items; next=0;} Page *left; // Pointer to the leftmost subtree Page *next; // Pointer to the adjacent node Item* items; int size; // Number of items on the page private: // Dont allow the copy constructor Page(const Page&); }; template class BTree { protected: Page* root; // Pointer to root node Item* buffer; // Buffer for distribution and merging int order; void FreePage (Page* page); bool SearchAux (Page* tree, KeyType key, Item* item); bool BinarySearch (Page* node, KeyType key, int* idx); Item* InsertAux (Item* item, Page* node); int DeleteItem(Item* items, int idx, int size); void DeleteAux1 (KeyType key, Page* node, bool* underflow); void DeleteAux2 (Page* parent, Page* node, int idx, bool* underflow); void Underflow (Page* node, Page* child, int idx, bool* underflow); int CopyItems (Item* src, Item* dest, int count); int InsertItem (Item* item, Item* items, int idx, int size); void PrintAux (Page* node, int margin); public: BTree (int order); ~BTree () {FreePage(root);} bool Search (KeyType key, Item* item) {return SearchAux(root, key, item);} void Insert (KeyType key, const DataType& data); void Delete (KeyType key); void Print (int margin = 0) {PrintAux(root, margin);} }; template class BPlusTree : public BTree { public: BPlusTree (int ord) : BTree(ord), leftLeaf(0) {} bool Search (KeyType key, Item* item) {return SearchAux(root, key, item);} void Insert (KeyType key, const DataType& data); void Delete (KeyType key); void LeafPrint(void); private: Page* leftLeaf; Item* InsertAux (Item* item, Page* node); bool SearchAux (Page* tree, KeyType key, Item* item); void DeleteAux1 (KeyType key, Page* node, bool* underflow); void Underflow (Page* node, Page* child, int idx, bool* underflow); }; template BTree::BTree (int ord) { if (ord < 1) ord=1; root=0; order=ord; buffer = new Item[2*order + 2]; } template void BTree::FreePage (Page* page) { if (page != 0) { FreePage(page->left); for (int i=0; isize; ++i) FreePage(page->items[i].right); delete page; } } template bool BTree::SearchAux (Page* tree, KeyType key, Item* item) { int idx; if (tree == 0) return false; if (BinarySearch(tree, key, &idx)) { *item = tree->items[idx]; return true; } if (idx < 0) return SearchAux(tree->left, key, item); else return SearchAux(tree->items[idx].right, key, item); } template bool BPlusTree::SearchAux (Page* tree, KeyType key, Item* item) { int idx; if (tree == 0) return false; if (BinarySearch(tree, key, &idx) && (tree->left==0)) // Also make sure it is a leaf node { *item = tree->items[idx]; return true; } if (idx < 0) return SearchAux(tree->left, key, item); else return SearchAux(tree->items[idx].right, key, item); } template bool BTree::BinarySearch (Page* node, KeyType key, int* idx) { int lowerBound=0; int upperBound=node->size-1; int middle; bool found; do { // Binary Chop middle = (lowerBound + upperBound) / 2; if (key <= node->items[middle].key) upperBound = middle - 1; // restrict to lower half if (key >= node->items[middle].key) lowerBound = middle + 1; // restrict to upper half } while (lowerBound <= upperBound); found = (lowerBound - upperBound) > 1; if (found) *idx = middle; else *idx=upperBound; return found; } template void BTree::Insert (KeyType key, const DataType& data) { Item* receive; Item item; Page* page; item.key = key; *(item.data) = data; item.right = 0; if (root == 0) // empty tree { root = new Page(order); root->left = 0; root->items[0] = item; root->size = 1; } else if ((receive = InsertAux(&item, root)) !=0) // propigate the root { page = new Page(order); page->size = 1; page->left = root; page->items[0] = *receive; root=page; } } template void BPlusTree::Insert (KeyType key, const DataType& data) { Item* receive; Item item; Page* page; item.key = key; *(item.data) = data; item.right = 0; if (root == 0) // empty tree { root = new Page(order); leftLeaf=root; // Only change in this function for BPlusTree is to assign the leftleaf to the root root->left = 0; root->items[0] = item; root->size = 1; } else if ((receive = InsertAux(&item, root)) !=0) // propigate the root { page = new Page(order); page->size = 1; page->left = root; page->items[0] = *receive; root=page; } } template Item* BTree::InsertAux (Item* item, Page* node) { Page *child, *page; int idx, size, half; if (BinarySearch(node, item->key, &idx)) return 0; // already in tree if (idx < 0) child = node->left; else child = node->items[idx].right; if (child !=0) item=InsertAux(item,child); // Child is not a leaf if (item != 0) { if (node->size < 2*order) node->size = InsertItem(item, node->items, idx+1, node->size); else { page = new Page(order); size = CopyItems(node->items, buffer, node->size); size = InsertItem(item, buffer, idx+1, size); node->size = CopyItems(buffer, node-> items, half = size/2); page->size = CopyItems(buffer+half+1, page->items, size-half-1); page->left = buffer[half].right; *item = buffer[half]; item->right = page; return item; } } return 0; } template Item* BPlusTree::InsertAux (Item* item, Page* node) { bool found; Page *child, *page; int idx, size, half; found = BinarySearch(node, item->key, &idx); // Decide whether or not the item is in the current node if (idx < 0) child = node->left; else child = node->items[idx].right; if (child !=0) item=InsertAux(item,child); // Child is not a leaf, it will always recurse whether the item was found or not if (item != 0 && !found) { if (node->size < 2*order) node->size = InsertItem(item, node->items, idx+1, node->size); else // Split the node { page = new Page(order); size = CopyItems(node->items, buffer, node->size); // copy the node to the buffer size = InsertItem(item, buffer, idx+1, size); // put the new item in the buffer node->size = CopyItems(buffer, node-> items, half = size/2); // copy the first half of the buffer back to the node page->size = CopyItems(buffer+half, page->items, size-half); // copy the second half of the buffer to the new node page->left = buffer[half].right; *item = buffer[half]; item->right = page; // Same as connecting a linked list. page->next=node->next; node->next=page; return item; } } return 0; } template void BTree::Delete (KeyType key) { bool underflow; DeleteAux1(key, root, &underflow); if (underflow && root->size == 0) // dispose root { Page* temp; temp=root; root = root->left; delete temp; } } // Same as regular, but calls the BPlusTree version of DeleteAux1 template void BPlusTree::Delete (KeyType key) { bool underflow; DeleteAux1(key, root, &underflow); if (underflow && root->size == 0) // dispose root { Page* temp; temp=root; root = root->left; delete temp; } } template void BTree::DeleteAux1 (KeyType key, Page* node, bool* underflow) { Page* child; int idx; *underflow = false; if (node==0) return; if (BinarySearch(node, key, &idx)) { if (idx - 1 < 0) child = node->left; else child = node->items[idx-1].right; if (child==0) // node is a leaf { node->size = DeleteItem(node->items, idx, node->size); *underflow = node->size < order; } else { DeleteAux2(node, child, idx, underflow); if (*underflow) Underflow(node, child, idx, underflow); } } else // Key is not in this node { child = (idx < 0 ? (*node).left : node->items[idx].right); DeleteAux1(key, child, underflow); if (*underflow) Underflow(node, child, idx, underflow); } } template void BPlusTree::DeleteAux1 (KeyType key, Page* node, bool* underflow) { Page* child; int idx; *underflow = false; if (node==0) return; if (BinarySearch(node, key, &idx) && ((*node).left == 0)) // Found, and is a leaf page { node->size = DeleteItem(node->items, idx, node->size); *underflow = node->size < order; } else // Key is not in this node { child = (idx < 0 ? (*node).left : node->items[idx].right); DeleteAux1(key, child, underflow); if (*underflow) Underflow(node, child, idx, underflow); } } template void BTree::DeleteAux2 (Page* parent, Page* node, int idx, bool* underflow) { Page* child = node->items[node->size-1].right; Page* right; if (child != 0) // node is not a leaf { DeleteAux2(parent, child, idx, underflow); // go another level down if (*underflow) Underflow(node, child, node->size-1, underflow); } else { right = parent->items[idx].right; // borrow an item from node for parent parent->items[idx]=node->items[node->size-1]; parent->items[idx].right=right; node->size = DeleteItem(node->items, node->size-1, node->size); *underflow = node->size < order; } } template void BTree::Underflow (Page* node, Page* child, int idx, bool* underflow) { Page* left = (idx < node->size-1 ? child : (idx==0 ? node->left : node->items[idx-1].right)); Page* right = (left==child ? node->items[++idx].right : child); int size, half; // copy contents of left, parent item, and right into the buffer size = CopyItems(left->items, buffer, left->size); buffer[size] = node->items[idx]; buffer[size++].right = right->left; size+= CopyItems(right->items, buffer+size, right->size); if (size>2*order) { // distribute the buffer between left and right left->size = CopyItems(buffer, left->items, half=size/2); right->size = CopyItems(buffer+half+1, right->items, size-half-1); right->left = buffer[half].right; node->items[idx]=buffer[half]; node->items[idx].right=right; *underflow=false; } else { // merge and free the right page left->size = CopyItems(buffer, left->items, size); node->size = DeleteItem(node->items, idx, node->size); delete right; *underflow = node->size < order; } } template void BPlusTree::Underflow (Page* node, Page* child, int idx, bool* underflow) { Page* left = (idx < node->size-1 ? child : (idx==0 ? node->left : node->items[idx-1].right)); Page* right = (left==child ? node->items[++idx].right : child); int size, half; // copy contens of left and right into the buffer size = CopyItems(left->items, buffer, left->size); size+= CopyItems(right->items, buffer+size, right->size); if (size>2*order) { // distribute the buffer between left and right. Overwrite the parent with the leftmost key of the right node left->size = CopyItems(buffer, left->items, half=size/2); right->size = CopyItems(buffer+half, right->items, size-half); node->items[idx]=buffer[half]; node->items[idx].right=right; *underflow=false; } else { // merge and free the right page left->size = CopyItems(buffer, left->items, size); node->size = DeleteItem(node->items, idx, node->size); left->next=right->next; delete right; *underflow = node->size < order; } } template int BTree::CopyItems (Item* src, Item* dest, int count) { for (int i=0; i < count; ++i) dest[i] = src[i]; return count; } template int BTree::InsertItem (Item* item, Item* items, int idx, int size) { for (int i = size; i > idx; --i) items[i] = items[i-1]; *(items+idx)=*item; return size+1; } template int BTree::DeleteItem(Item* items, int idx, int size) { for (int i=idx; i < size-1; ++i) items[i] = items[i+1]; return size-1; } template void BTree::PrintAux (Page* node, int margin) { char marginBuffer[128]; if (node!=0) { for (int i =0; i <=margin; ++i) marginBuffer[i]=' '; marginBuffer[i]=0; PrintAux(node->left, margin+8); for (i=0; i < node->size; ++i) { cout << marginBuffer << '(' << node->items[i].key << ',' << *(node->items[i].data) << ")\n"; PrintAux(node->items[i].right, margin+8); } } } template void BPlusTree::LeafPrint (void) { Page *current=leftLeaf; while (current) { for (int i=0; i < current->size; ++i) cout << '(' << current->items[i].key << ',' << *(current->items[i].data) << ")\n"; current=current->next; } } void main(void) { int key, key1, key2; char option[20]; Item item; BTree tree(2); while (true) { cout << "\nS>earch, I)nsert, D)elete, P)rint, L)eaf_Print Q)uit ?"; cin >> option; if (isupper(*option)) *option = tolower(*option); switch (*option) { case 's': cout << "key? "; cin >> key; if (tree.Search(key, &item)) cout << "data = " << *(item.data) << "\n"; else cout << "no such item.\n"; break; case 'i': cout << "from, to? "; cin >> key1 >> key2; for (key=key1; key<=key2; key+=5) tree.Insert(key,key+.5f); break; case 'd': cout << "key? "; cin >> key; if (tree.Search(key, &item)) tree.Delete(key); else cout << "no such item.\n"; break; case 'p': tree.Print(); break; // For Bplus tree only. Comment this case out for regular BTrees //case 'l': // tree.LeafPrint(); // break; case 'q': exit(0); } } } #endif