Assignment 3 - Performance Testing of a Custom Database

Introduction to Assignment 3: SEE600 Assignment3.mp4.

Due - Sunday, March 23, 2025

This is a group project of 2 or 3 students per group. The groups can be found in the document Assignment3_Groups.docx.

Introduction

We want a database that is fast and uses little memory. We have limited CPU power and limited RAM. We are running real-time software (event driven) which must respond quickly to events and requests. A standard database package such as MySQL is too large and too slow for our constrained environment. Should we implement our database using std::map of the standard C++ library or construct our own custom database based on AVL trees?

The AVL Tree

A tree is perfectly balanced if it is empty or the number of nodes in each subtree differ by no more than 1. In a perfectly balanced tree, we know that searching either the left or right subtree from any point will take the same amount of time.

The search time in a perfectly balanced tree is O(log n) as the number of nodes left to consider is effectively halved with each node considered. However, to get a tree to be perfectly balance can require changing every node in the tree. This makes trying to create a perfectly balanced tree impractical.

An AVL tree does not create a perfectly balanced binary search trees. Instead it creates a height balanced binary search tree. A height balanced tree is either empty or the height of the left and right subtrees differ by no more than 1. A height balanced tree is at most 44% taller than a perfectly balanced tree and thus, a search through a height balanced tree is O(log n). Insert and delete can also be done in O(log n) time.

Height Balance

AVL trees work by ensuring that the tree is height balanced after an operation. If we were to have to calculate the height of a tree from any node, we would have to traverse its two subtrees making this impractical. Instead, we store the height balance (or height) information of every subtree in its node. Thus, each node must not only maintain its data and children information, but also a height balance (or height) value.

The height balance of a node is calculated as follows:

    height balance = height of right - height of left
         of node      subtree             subtree

Reference Material

For more information on the AVL tree, see the course notes of BTP500: AVL Trees.
For an introduction to AVL Trees, see the video: AVL Trees Introduction.
For a visualization of the algorithm for insertion and deletion with an AVL tree, see AVL Tree Algorithm Visualization.

Black Box Performance Testing

You have been given code for an AVL tree for both Windows and Linux. The only real difference is that the Linux version can build a bigger tree. The code can be seen as follows:
Windows: timer.h, timer.cpp, AVLTree.cpp.
Linux: Makefile, timer.h, timer.cpp, AVLTree.cpp.

Task 1: You need to clean this code a little. What could you do to facilitate the reuse of this tree in other company projects?

Even though you can see the source code, this effectively is black-box testing, because you will perform tests through the AVL Tree class interface without inspecting the code you are working with.

Now you need to write code to perform tests to see if your custom database based in the AVL tree is "better" than a database based on std::map. You have decided on the following tests in the Windows operating system:

1. Test for correctness of insertion.
2. Test for correctness of deletion.
3. Test for maximum size.
4. Test for load (have the tree repeatedly accessed).
5. Test for memory leak.
6. Test for speed of search (worst case).

Writing Test Code

Your test code should perform all the required tests (with the exception for the test for the memory) in one execution cycle, for both std::map and for the AVL tree. You should have separate code for Windows and Linux. Consider the following:

• You might wish to insert pauses between tests, such as "press any key to continue".
• You might wish to give a print-out after each test.
• Tests 1 and 2 can be performed with hard-coded data, where you insert data, or delete data, then execute the display function of your AVL Tree class and compare with the expected. You can use visualization software to help you determine what the expected should be.
• Test 3 should attempt to create an AVL tree of a given size. If successful, delete the tree and then create one of a bigger size. Keep going until you trigger something lika an std::bad_alloc exception. Your code should not crash. Try to come close to that maximum tree size.
• Test 4 could repeated call the insert function (perhaps thousands of time) with no delays.
• Test 5 can be performed with standard memory leak detection software such as valgrind.
• Test 6 should attempt to search for the hardest to reach node in the tree. Since the tree is sorted according to the social insurance number, the lowest and highest sin's will be at the base of the tree.

Questions

1. Are there any other test that you feel are required? Describe them briefly.
2. Compare and contrast std::map vs AVL tree for all six test cases above.
   • Were there unexpected results?
   • Which would you recommend, std::map or AVL Tree?
   • Based on memory tests, what maximum memory would you recommend be reserved for the database?
3. Is this AVL Tree reusable for other projects?
4. Is your test software reusable?

Marking Rubric

You will be marked out of 10 according to the following:

Submission

Please email all source code and answers to questions to: miguel.watler@senecapolytechnic.ca

Your answers to questions can be submitted in a separate document or embedded within your source code.

Late Policy

You will be docked 10% if your assignment is submitted 1-2 days late.
You will be docked 20% if your assignment is submitted 3-4 days late.
You will be docked 30% if your assignment is submitted 5-6 days late.
You will be docked 40% if your assignment is submitted 7 days late.
You will be docked 50% if your assignment is submitted over 7 days late.