Keyed DB

A light-weight Node.js/TypeScript library to manage a sorted & indexed collection with pagination support. All done using binary search.

Originally based on Swift code written for Queenfisher.

Install

npm i @thehackingguard/keyed-db

Running Tests

npm test

Quick Start

CommonJS

const KeyedDB = require('@thehackingguard/keyed-db')

ESM/TypeScript

import KeyedDB from '@thehackingguard/keyed-db'

Constructor

const db = new KeyedDB<T>(
  { key: t => t.uniqueNumberKeyProperty },
  t => t.optionalUniqueIDProperty
)

With a custom comparison:

const db = new KeyedDB<T>(
  {
    key: t => t.someProperty,
    compare: (t1, t2) => t1 < t2 ? -1 : t1 > t2 ? 1 : 0
  },
  t => t.optionalUniqueIDProperty
)

Functions

db.insert(value)                // insert value in DB
db.upsert(value)                // upserts value
db.insertIfAbsent(value)        // only inserts if not already present in DB
db.delete(value)                // delete value
db.deleteById(id)               // delete value by referencing the ID
db.updateKey(value, updater)    // update the key of a value & re-place it
db.paginated(cursor, limit)     // get X results after the given cursor (null for the first page)

Usage Example

import KeyedDB from '@thehackingguard/keyed-db'

type Chat = {
  timestamp: Date
  chatID: string
}

const db = new KeyedDB<Chat>(
  { key: value => value.timestamp.getTime() * -1 },
  value => value.chatID
)

for (let i = 0; i < 1000; i++) {
  db.insert({
    timestamp: new Date(new Date().getTime() - Math.random() * 10000),
    chatID: `person ${i}`
  })
}

console.log(db.all())
console.log(db.paginated(null, 20))
console.log(db.paginated(null, 20, null, 'before'))
console.log(db.paginated(null, 20, chat => chat.chatID.includes('something')))

const someDate = new Date().getTime()
const cursorPaginated = db.paginated(someDate, 20)
console.log(cursorPaginated)

db.delete(cursorPaginated[0])
db.updateKey(cursorPaginated[1], value => (value.timestamp = new Date()))

Time Complexity

| Operation | Time Complexity | |----------------|-----------------| | db.insert() | O(logN) | | db.delete() | O(logN) | | db.get() | O(1) | | db.updateKey() | O(logN) |

License

GPL-3.0.

Attribution

Published as @thehackingguard/keyed-db. Derived from original keyed-db work by adiwajshing (GPL licensed). All original notices and GPL-3.0 terms are preserved.