"Binary Search Tree (assume that it is balanced)" "Closed Hash Table" "Linear Index" B+ Tree Khan.randRange(0,1) Khan.randRange(0,1) Khan.randRange(0,1) [ "static database (no inserts or deletes)", "dynamic database (supports inserts and deletes)" ] [ "on disk", "in main memory" ] [ "support range queries", "perform exact mach queries only", ] 4*QUERYTYPE+2*STORAGE+DATABASETYPE [ LINEAR, BPTREE, LINEAR, BST, HASH, HASH, HASH, HASH ]

You are to select one of the choices for an indexing structure when used under the conditions indicated.

The system will QARRAY[QUERYTYPE], when stored SARRAY[STORAGE], working on a DARRAY[DATABASETYPE].

ANSWER[INDEX]
  • BST
  • HASH
  • LINEAR
  • BPTREE

A Closed Hash Table is always great for exact-match queries, and always terrible for range queries.

A Linear Index is bad for dynamic databases. It is a little more efficient than the alternatives for static databases.

The B+ Tree is great on disk, but has too much overhead to be practical for in-memory applications.

A balanced BST is not good on disk, but works well for in-memory applications.