US Patent 9514170 Priority queue using two differently-indexed single-index tables

Methods and apparatus for efficient priority queues using single-index tables are disclosed. In response to a request to generate an instance of a priority queue using a database that permits no more than one index per table, an identifier-indexed table and a priority-indexed table are set up. In response to a request to insert a queue entry with a given identifier and a given priority, one tuple is inserted into each table. In response to a request to remove an entry with a specified identifier, a tuple with the specified identifier is removed from the identifier-indexed table, while the removal of the corresponding tuple from the priority-indexed table may be deferred.