BTree Test Page

These tests require that the file "keys" be in the same directory as the Minibase executable.

The Btree tests periodically stop to allow the user to examine individual pages in the tree. The header, root, internal and leaf pages may be examined to see what pages are next to one another. A visual interface is added to visualize the structure of the tree.

Test 1

Create an index and insert key / rid pairs into it. In Test 1 keys are integers. The keys are inserted in ascending order. The maximum number of keys that can be inserted into the tree is set at 4000 (enough to create three levels of the tree). A random deletion of 10% of the key/rid pairs is done.

Test the range scans: All Scan, Max Range Scan, Min Range Scan, and Min-Max Range Scan. Also Exact Match. Delete current is done as well. The tree is not destroyed because Test 2 uses it.

Test 2

In Test 2, scans are performed that make no sense (e.g., low values higher than the high values, etc.). The index that was created in Test 1 is used for testing these scans. The scans should return no tuples. They should not return any errors. Finally, the Btree index is destroyed.

Test 3

In this test, the full deletion algorithm is exercised. After inserting 2000 integer key/rid pairs, 1950 of these are deleted. 2000 keys are sufficient to create two levels of the tree. At this point, the user is allowed to examine the root and leaf pages. Due to the deletions, the root page is converted back to a leaf page (from an index page) as it can hold 50 records. Again, various scans are tested and then the index is destroyed.

Test 4

Basically the same as Test 1 and Test 2 combined, except that instead of an integer key, a string is used. The keys read from the file "keys" (in the same directory as the Minibase executable) are inserted in lexicographic order. Deletion of a particular key and different types of scans as in Test 1 are done. Like in Test 2, abnormal scans are tested. Finally, the index is destroyed.


BTree Page
Back to the Components Page
Back to the Minibase Home Page