Skip to main content

Indexes

Setup shared by the examples on this page
import { OIMDB, OIMEffectService, OIMReclaimingIndexKeysService, OIMSetBucketContentService, OIMSlotAtUnholdReleasePolicy, createOIMComputedService, createOIMSortedComputedService, createOIMSlotCollectionIndexService, createOIMSlotCollectionSortedArrayIndexService, isOIMSameSlotSequence, type TOIMEntitySlot, createOIMEntityContentService, createOIMSlotCollectionService, OIMSlotTreeStoreService, OIMDefaults, type TOIMBucketSlot, type TOIMBucketSlotsArrayStore, type TOIMStoreKey, OIMScalarKeyTreeWalk } from '@oimdb/core';

type Card = { id: string; deck: string; rank: number };

declare function render(value?: unknown): void;

const db = new OIMDB();
const effectService = OIMEffectService.INSTANCE;
const cardService = createOIMSlotCollectionService({ slotContentService: createOIMEntityContentService<Card>() });
const cards = cardService.createStoreSlot(db);
const cardContentService = cardService.slotContentService;

const byRank = (leftBucketMemberSlot: TOIMEntitySlot<Card>, rightBucketMemberSlot: TOIMEntitySlot<Card>): number =>
(leftBucketMemberSlot.entity?.rank ?? 0) - (rightBucketMemberSlot.entity?.rank ?? 0);

An index is a bucket collection whose buckets are filled from an entity store slot by selectKey: every write to the source decides which bucket the entity belongs to. Its buckets are the same buckets a caller fills by hand; why it is shaped this way is on Why an index looks like this.

How an index files entities​

Use an index when the bucket an entity belongs to is a function of the entity (card.deck, a status, an owner id), so every write can decide it. When the members come from a response instead, take a manual bucket collection. Why an index is a pushed bucket plus a pulled order is on its own page: Why an index looks like this.

Entity collectionwriteSlotContentByKey, updateEntity, clearSlotContent
→
IndexselectKey or columns gives each entity its key; a write that moves the key refiles it
→
bucket 'todo'the entity slots with that key
bucket 'done'one bucket per key, minted when the key is first filed or asked for
→
Sorted viewcreateOIMSortedComputedService: one ordered array per bucket, re-sorted only when membership or a sort column moves
→
Componentsubscribes to the one bucket or view it shows

The index service is built once per entity collection type; createIndexStoreSlot(entityStoreSlot) builds one index over one entity store slot, and returns the index's own store slot of buckets.

Setup shared by the examples on this page
const deckIndexService = createOIMSlotCollectionIndexService({
entityService: cardService, // the entity collection it reads
selectKey: (card: Card) => card.deck, // which key an entity belongs to
});
const deckIndex = deckIndexService.createIndexStoreSlot(cards);
const deckBucketReads = deckIndexService.slotContentService;
const red = deckIndexService.holdSlotByKey(deckIndex, 'red'); // the bucket; minted on first hold
cardService.writeSlotContentByKey(cards, 'c1', { id: 'c1', deck: 'red', rank: 1 });
db.flush();

Array.from(deckBucketReads.getBucketMemberSlots(red)); // [c1]

createOIMSlotCollectionIndexService(options) builds the index over a Map store of buckets. Its options:

OptionDefaultWhat it decides
entityServicerequiredthe source collection service; only its getSlots is used, to fill a new bucket
columns / selectKeyone of them requiredwhere the key comes from
slotContentServicenew OIMPositionalArrayBucketContentService(), with no recorderhow a bucket holds its slots: pass new OIMSetBucketContentService() for no order, or one built with bucketCommands for a render script
bucketSlotStoreServicea Map store; required for an array keywhere buckets are filed
slotReleasePolicydefaults.slotReleasePolicy, then OIMSlotAtEmptyReleasePolicy.INSTANCEhow long a bucket lives
columnSlotStoreService / columnNamesa shared map-driven storewhere bucket column slots live

The index-keys strategy comes from defaults (new OIMDefaults({ indexKeysService }), see below). A key of several columns takes the composite-key door, which sets a tree-driven store.

const unorderedDeckIndexService = createOIMSlotCollectionIndexService({
entityService: cardService,
selectKey: (card: Card) => card.deck,
slotContentService: new OIMSetBucketContentService<TOIMEntitySlot<Card>>(),
});
const unorderedDeckIndex = unorderedDeckIndexService.createIndexStoreSlot(cards);

The default buckets keep arrival order. Only the array-based content services answer by position: getBucketMemberSlotAt(bucketSlot, index) reads the array at that index, O(1), and getBucketMemberSlotPosition(bucketSlot, entitySlot) walks the array, O(n), returning -1 for a slot that is not a member. A set has no positions, so a set-driven index has neither. Take the set-driven one when you read neither arrival order nor positions: its membership test and removal are a hash lookup.

OIMSlotCollectionIndexService is a collection service of buckets, so it has every read door of one. Its slotContentService is the bucket content service narrowed by type to its reads — the index is the only writer of its buckets. A door that names a key takes the index's store slot first; a door on a bucket takes only the bucket slot:

DoorsWhat for
getSlotByKey, holdSlotByKey, peekSlotByKey, hasSlotContentByKey, getSlotsByKeys, holdSlotsByKeys, slot.owner.unholdSlotthe bucket of a key
slotContentService.getBucketMemberSlots, getBucketMemberSlotCount, hasBucketMemberSlot; getEntitiesByKey(indexStoreSlot, key)what a bucket holds
slotContentService.getBucketMemberSlotAt, getBucketMemberSlotPositionpositional reads, on an array-based content service only
getSlots, getSlotCountwhich buckets are filed
getAnyBucketColumnSlotByKey, holdAnyBucketColumnSlotByKeythe bucket's any-column slot
getBucketColumnSlotByKey, holdBucketColumnSlotByKey, unholdColumnSlotbucket column slots; unholdColumnSlot also gives back an any-column slot
disposeIndexStoreSlottaking one index off its source

The channel slot of an index store slot is its source store slot's.

Where the key comes from: columns, selectKey, or both​

The same pair as the sorter's sortColumns / comparator:

const byColumn = createOIMSlotCollectionIndexService({ entityService: cardService, columns: ['deck'] });
const byFunction = createOIMSlotCollectionIndexService({ entityService: cardService, selectKey: (card: Card) => card.deck });
const byFunctionOfColumns = createOIMSlotCollectionIndexService({
entityService: cardService,
columns: ['deck'],
selectKey: (card: Card) => card.deck.toLowerCase(),
});
  • columns alone with ONE column: the key is its value, typed by TOIMIndexKey from that column, which must hold a store key. Several columns make a composite key, the array of their values in that order, and take the composite-key door — see A key of several columns.
  • selectKey alone is any function, and it runs again on every write to the source: a function does not say which columns it reads.
  • Both: the columns are the ones selectKey reads.

With columns, a patch or put whose changed columns include none of them keeps the entity's key and calls nothing. A write of the whole value — a fill, a clear, markEntityChanged(slot) with no names — always reads the key again.

A slot with no entity is filed under no bucket, and neither is an entity whose selectKey returns undefined. createOIMSlotCollectionIndexService constrains the key to TOIMStoreKey unless it is handed a bucketSlotStoreService, createOIMSlotCollectionIndexService to an array of TOIMStoreKey, and a key type handed to them by hand must be assignable to the one TOIMIndexKey computes from columns.

A key of several columns​

An array key needs a bucket store that compares arrays part by part: pass bucketSlotStoreService, an OIMSlotTreeStoreService over OIMScalarKeyTreeWalk.INSTANCE. Name two or more columns and the key is the array of their values, in that order:

type PlayingCard = { id: string; deck: string; suit: string };

const playingCardService = createOIMSlotCollectionService({ slotContentService: createOIMEntityContentService<PlayingCard>() });
const playingCards = playingCardService.createStoreSlot(db);
type TDeckAndSuitBucket = TOIMBucketSlot<TOIMBucketSlotsArrayStore<TOIMEntitySlot<PlayingCard>>, readonly [string, string]>;
const byDeckAndSuitService = createOIMSlotCollectionIndexService({
entityService: playingCardService,
columns: ['deck', 'suit'],
selectKey: (card: PlayingCard): readonly [string, string] => [card.deck, card.suit],
bucketSlotStoreService: new OIMSlotTreeStoreService<TOIMStoreKey, TDeckAndSuitBucket>(OIMScalarKeyTreeWalk.INSTANCE),
});
const byDeckAndSuit = byDeckAndSuitService.createIndexStoreSlot(playingCards);
byDeckAndSuitService.getEntitiesByKey(byDeckAndSuit, ['red', 'hearts']);
  • The key type comes from the columns (TOIMIndexKey<TEntity, TColumns>): one column is that column's value without undefined, several are a tuple of their values, so ['deck', 'suit'] above is keyed by readonly [string, string] and a one-column index refuses an array. Columns must be written inline or as const: a string[] variable carries no length, so its key could be either a value or an array, and both doors refuse it.
  • The index's bucket store is that OIMSlotTreeStoreService. To tell whether an entity's key moved, the index asks its bucket store isSameKey.
  • A selectKey returning an array of TOIMStoreKey takes createOIMSlotCollectionIndexService with a tree store passed as bucketSlotStoreService.
  • Each write that reads the key builds one array; a fresh array with the same parts is the same key, so it moves nothing and wakes nothing.
  • getSlotsByKeys / holdSlotsByKeys fill every new bucket either way, but only a scalar key gets the ONE pass over the source: array keys are filled one pass per key, the cost of calling getSlotByKey for each.

No bucket exists for a key until it is minted. A bucket minted through any door (getSlotByKey, holdSlotByKey, getSlotsByKeys, holdSlotsByKeys, getEntitiesByKey) is filled with the source entities written before it, without a flush, so minting inside an effect body does not throw. getSlotsByKeys / holdSlotsByKeys fill all new buckets in ONE pass over the source — take them when you mint many keys at once, such as every column of a board.

The usual way to consume one is an effect on the bucket:

const red = deckIndexService.holdSlotByKey(deckIndex, 'red');

effectService.createAndRunEffect(db, () => render(Array.from(deckBucketReads.getBucketMemberSlots(red))), [red]);

The bucket wakes on membership only — an entity joining or leaving it. A write to an entity that stays in the bucket does not wake it; each entity is subscribed to through its own slot.

What a write costs, and how long a bucket lives​

  • A key with no bucket is not maintained at all. No slots, no service calls — an entity arriving under such a key costs one key read, one comparison and, when its key changed, one write of its index-key cell. What decides it is whether the bucket exists, not whether anyone holds it: while a bucket stands it is maintained, held or not, and a key whose bucket was released goes back to costing nothing.
  • Entities are filed on write, using the index's key, through the source store slot's content-change hook.
  • A bucket's lifetime is the slotReleasePolicy, not the index's. Name nothing (here or on the db) and you get OIMSlotAtEmptyReleasePolicy.INSTANCE: an unheld bucket stays, and goes on being maintained, while it has members, and goes once it is empty. Pass OIMSlotNeverReleasePolicy.INSTANCE and a bucket stands for good; new OIMSlotAfterIdleReleasePolicy({ keepAfterIdleMs }) and it cools on the queue; OIMSlotAtUnholdReleasePolicy.INSTANCE and it ends at the last give-back, and the next hold builds a fresh one with one scan of the source. The policies themselves: Releasing an identity on a clock.
  • Order is not the bucket's business. A sorted list is createOIMSortedComputedService over the index service (Ordering). Compose a second computed over the bucket for filtering or any other order.
const deckIndexOnlyWhileHeldService = createOIMSlotCollectionIndexService({
entityService: cardService,
selectKey: (card: Card) => card.deck,
slotReleasePolicy: OIMSlotAtUnholdReleasePolicy.INSTANCE,
});
const deckIndexOnlyWhileHeld = deckIndexOnlyWhileHeldService.createIndexStoreSlot(cards);

Use OIMSlotAtUnholdReleasePolicy when keys are many and each is looked at briefly (a details panel per user); keep the default when a few keys are read over and over.

An order of your own is a derivation over the bucket:

const rankedInDeckService = createOIMComputedService<string, readonly TOIMEntitySlot<Card>[]>({
createSources: ({ key }) => ({
sourceSlots: [deckIndexService.getSlotByKey(deckIndex, key)],
}),
derive: (computedSlot) => Array.from(
deckBucketReads.getBucketMemberSlots(deckIndexService.getSlotByKey(deckIndex, computedSlot.key)),
).sort(byRank),
sameValueGuard: isOIMSameSlotSequence,
initialValue: [],
});
const rankedInDeck = rankedInDeckService.createStoreSlot(db);

The bucket is named in sourceSlots, so the computed holds it for as long as the composed order is filed.

Disposing an index​

createIndexStoreSlot(entityStoreSlot) is the whole wiring of one index: it registers a content-change listener on that store slot (OIMSlotContentChangeListenerService.INSTANCE), and the entity collection knows nothing about indexes. disposeIndexStoreSlot(indexStoreSlot) unsubscribes that index from its source, empties its buckets and gives back every entity slot it held. The minting doors on that index store slot (getSlotByKey, holdSlotByKey, getSlotsByKeys, holdSlotsByKeys, getEntitiesByKey, the bucket column doors) throw after it, because the index no longer hears its source; the give-backs (slot.owner.unholdSlot, unholdColumnSlot) still work, so a consumer tearing down after the index does not have to know the order. The index service and its other store slots are untouched.

const temporaryIndex = deckIndexService.createIndexStoreSlot(cards);
deckIndexService.disposeIndexStoreSlot(temporaryIndex);

The bucket's any-column slot​

For a reader that needs the whole list every time a member's content changes, the index hands out a bucket's any-column slot: getAnyBucketColumnSlotByKey(indexStoreSlot, key) and holdAnyBucketColumnSlotByKey(indexStoreSlot, key), given back with unholdColumnSlot. It is a TOIMColumnSlot on the bucket slot, and it wakes when any column of any member of that bucket changes and when a member joins or leaves, because its value lists the members' entities. The bucket slot (getSlotByKey / holdSlotByKey) wakes on membership alone.

const redBucket = deckIndexService.holdSlotByKey(deckIndex, 'red');
const redAnyColumn = deckIndexService.holdAnyBucketColumnSlotByKey(deckIndex, 'red');
const redEffect = effectService.createEffect(db, () => {
render(deckIndexService.getEntitiesByKey(deckIndex, 'red'));
}, [redBucket, redAnyColumn]);
effectService.disposeEffect(redEffect);
redAnyColumn.unholdSlot();
redBucket.unholdSlot();

Do not use it to render a list. One edit of one entity wakes the whole list, so a view bound to it re-renders every item for a one-field change. Subscribe the list to the bucket and each entity to its own slot. The any-column slot is for an export, an aggregate over the entities, or a log.

It costs nothing until asked for: an entity write is checked against it only after the first getAnyBucketColumnSlotByKey / holdAnyBucketColumnSlotByKey. A getAnyBucketColumnSlotByKey nobody kept is gone at the next flush().

The content-change hook and indexKeys​

An index is a content-change listener on its source store slot. To push a derivation per write the way an index does, add your own with OIMSlotContentChangeListenerService.INSTANCE.addContentChangeListener(storeSlot, listener, readColumnNames) and remove it with removeContentChangeListener(storeSlot, listener). An IOIMSlotContentChangeListener has onContentChanged(slot, patch, changedColumns) and onManyContentsChanged(...), which a batch write calls once. readColumnNames undefined means every column. addContentChangeListener returns the listener's TOIMSlotContentChangeListenerReadColumns (declaredColumnNames, addedColumnNames, isAnyColumnAdded); addListenerReadColumn(storeSlot, listener, columnName) and addListenerReadAnyColumn(storeSlot, listener) add reads to it later, and the util isOIMAnyAddedColumnRead(listenerReadColumns, changedColumns) tells whether a write hit one of them. Listeners on one store slot share one column filter, so a listener still checks changedColumns itself. Anything that can be pulled belongs in a computed instead.

Each entity slot remembers, per index, the key it is filed under, so a moved entity leaves its old bucket in O(1). How that memory is kept is chosen by the defaults an index is built with, new OIMDefaults({ indexKeysService }):

strategyon disposeIndexStoreSlotcost
OIMAppendingIndexKeysService (default)the index's position is not reusedeach index ever created on a source leaves one entry on the slots it filed
OIMReclaimingIndexKeysServicethe position is wiped on every slot of the source and reusedO(N) per dispose
const shortLivedIndexDefaults = new OIMDefaults({ indexKeysService: new OIMReclaimingIndexKeysService() });
const byRankService = createOIMSlotCollectionIndexService({ defaults: shortLivedIndexDefaults, entityService: cardService, selectKey: (card: Card) => card.rank });

Switch to OIMReclaimingIndexKeysService only if you create indexes dynamically and often. That is expensive, so avoid it.

Ordering​

A bucket never sorts, except the bucket of a createOIMSlotCollectionSortedArrayIndexService index. Its order is what the caller or the arrivals put in: addBucketMemberSlots appends, insertBucketMemberSlotAt inserts, a move moves, writeSlotContent takes the sequence given. A sorted list is a computed over an index — createOIMSortedComputedService({ indexService, sortColumns?, comparator? }), then createSortedStoreSlot(indexStoreSlot) for each index — or the index sorts its own buckets, see Sorted at write. Take it when the order is a function of the entities' columns; take positions when the user decides it.

const cardsInDeckService = createOIMSlotCollectionIndexService({
entityService: cardService,
selectKey: (card: Card) => card.deck,
});
const cardsInDeck = cardsInDeckService.createIndexStoreSlot(cards);
const cardsByRankService = createOIMSortedComputedService({
indexService: cardsInDeckService,
sortColumns: [{ columnName: 'rank', direction: 'asc' }],
});
const cardsByRank = cardsByRankService.createSortedStoreSlot(cardsInDeck);

const red = cardsByRankService.holdSlotByKey(cardsByRank, 'red');
effectService.createAndRunEffect(db, () => { render(red.value); }, [], [red]);
red.unholdSlot();
  • indexService is the OIMSlotCollectionIndexService whose buckets the sorted list reads, and the index store slot handed to createSortedStoreSlot is the index it reads them from. The sorted service takes no db: its store slots run on the index store slot's channel slot.

  • sortColumns — TOIMSortColumn<TEntity>[], each { columnName, direction: 'asc' | 'desc' }, column a TOIMSortableColumnName<TEntity> (string, number or bigint values) — decide which writes re-sort.

  • comparator: (left: TEntity, right: TEntity) => number decides the order. Without it the order is createOIMColumnsComparator(sortColumns): the columns in turn, an undefined or null value last in either direction. An entity slot whose entity is gone sorts last.

  • Only comparator → any write to a member re-sorts. Neither → a member keeps the place it first took and an arrival is appended.

  • Both → the two split the job: comparator orders, and sortColumns is the list of columns whose change wakes the sort. List every column the comparator reads. A change to a column it reads but sortColumns omits does not re-sort — the list keeps its old order until something listed changes. Reach for this when the order needs a rule createOIMColumnsComparator cannot express (a locale compare, a computed key, a tie-break) and you still want the sort to wake only for the columns that rule reads, instead of for every write to a member as with comparator alone:

    type TitledCard = { id: string; deck: string; title: string; rank: number; note: string };
    const titledCardService = createOIMSlotCollectionService({ slotContentService: createOIMEntityContentService<TitledCard>() });
    const titledCards = titledCardService.createStoreSlot(db);
    const titledCardsInDeckService = createOIMSlotCollectionIndexService({
    entityService: titledCardService,
    selectKey: (card: TitledCard) => card.deck,
    });
    const titledCardsInDeck = titledCardsInDeckService.createIndexStoreSlot(titledCards);
    const byTitleInGermanService = createOIMSortedComputedService({
    indexService: titledCardsInDeckService,
    sortColumns: [{ columnName: 'title', direction: 'asc' }, { columnName: 'rank', direction: 'asc' }],
    comparator: (left, right) => left.title.localeCompare(right.title, 'de') || left.rank - right.rank,
    });
    const byTitleInGerman = byTitleInGermanService.createSortedStoreSlot(titledCardsInDeck);
    // a write to `title` or `rank` re-sorts; a write to any other column does not

It re-sorts only when the bucket's membership changed or a write changed one of its columns on a member: its sources are the bucket slot of the key plus the bucket column slot of each column (or the bucket's any-column slot when only a comparator is given). Its slots are computed slots: pulled, re-derived on the read that asks, subscribed to in the sourceComputeds list of createEffect. Read the value through slot.value, which settles the order before answering. A re-sort that yields the same sequence keeps the previous array, so a consumer memoising on identity needs no comparison of its own. The sorted array names each member slot once, even over a bucket that names one twice. Why this is a pull and membership is a push: Why an index looks like this.

Bucket column slots. An index hands out one column slot per bucket and column — getBucketColumnSlotByKey(indexStoreSlot, key, columnName), holdBucketColumnSlotByKey(indexStoreSlot, key, columnName), unholdColumnSlot(columnSlot). It is a TOIMColumnSlot whose carrierSlot is the bucket slot, written when a write changes that column on any member of the bucket and when a member joins or leaves (its value is that column across the members). Subscribe to one when you need "some member's rank moved" without "some member's title moved":

const rankInRed = deckIndexService.holdBucketColumnSlotByKey(deckIndex, 'red', 'rank');
const onRankInRed = effectService.createEffect(db, () => { render(); }, [rankInRed]);
effectService.disposeEffect(onRankInRed);
rankInRed.unholdSlot();

An index marks bucket column slots only once somebody has asked for one, so an index nobody sorts pays nothing for them.

A comparator that throws is thrown at the reader that asked — out of the sorted computed's getValueForSlot. The derive is not stamped as run, so the next read runs the comparator again; the bucket under it is untouched.

Sorted at write​

The sorted computed above sorts at read, over any index. The other arm keeps the index's own buckets in order, so a read needs no computed. You pick one at construction: createOIMSlotCollectionSortedArrayIndexService({ entityService, columns? | selectKey?, sortColumns, bucketCommands?, bucketSlotStoreService?, slotReleasePolicy?, columnSlotStoreService? | columnNames? }) returns an OIMSlotCollectionSortedArrayIndexService. sortColumns is the same TOIMSortColumn<TEntity>[] that createOIMSortedComputedService takes, and it is required.

const cardsByDeckService = createOIMSlotCollectionSortedArrayIndexService({
entityService: cardService,
columns: ['deck'],
sortColumns: [{ columnName: 'rank', direction: 'asc' }, { columnName: 'id', direction: 'desc' }],
});
const cardsByDeck = cardsByDeckService.createIndexStoreSlot(cards);
const spades = cardsByDeckService.holdSlotByKey(cardsByDeck, 'spades');
Array.from(spades.getBucketMemberSlots());
cardsByDeckService.slotContentService.getBucketMemberSlotAt(spades, 0);
  • Reads come back in order. getBucketMemberSlots, getBucketMemberSlotAt and getBucketMemberSlotPosition answer in sortColumns order.
  • Sorted on the first read. A write appends the arrival to an unsorted tail, and the first read settles it. A bucket nobody reads is not sorted.
  • A member is re-filed when one of its sort columns changes, and only then. A write to a column that is neither the key nor a sort column neither reorders the bucket nor wakes it.
  • There are no positional writes on this bucket. The order belongs to the comparator, so insertBucketMemberSlotAt and the other position writes stay on OIMPositionalArrayBucketContentService.
  • The render script is the whole list. Given bucketCommands, the bucket records every change as isWholeListRecorded and no commands, because the next settle could move any position a command would name. A view over it rebuilds from getBucketMemberSlots() in the frame the bucket changed; without bucketCommands nothing is recorded.

Which arm to take: sort-at-write suits point updates, where a rank change re-files one member. Sort-at-read suits bulk loads. Both ship; neither is the default.

Where to next​