(1) give O() analysis for insert/delete/search records with multi-level index, hashing, B-trees and ordered tables (ie. like Vertica). Assume the input table has an index on the primary key or it is ordered by the PK. Extend your analysis to blocks and disk access, transfer to RAM.
(2) analyze time complexity in terms of # of records and # of blocks of the 4 fundamental joins algorithms. Make the analysis on two tables T1 and T2, with sizes M and N which may or may not have the same size, and wehich may or may not have different record size. This analysis only requires big O(). Extend your join analysis to a cost model assuming a finite amount of RAM, smaller than disk. This analysis requires you to consider disk access. Assume disk access when there is seek it is 1000X slower than RAM random access. However, if doing sequential access assume disk is just 10X slower. Give time estimation based on # of bytes read/written.
(3) compare 2PL and timestamping for N transactions T1..T_N, executed by M threads where M<
(4) Briefly compare disk and solid state memory to read/write blocks of records using all the algorithms and data structures above. You can assume blocks of records have seek/read/write operations and you are evaluating SPJ queries in SQL.
Required minimum 5-7 page