Inverted indexes are what databases call indexes. It's used in the IR field to differentiate from forward indexes, which are less common, so you're right that we could just say "index's.

But when we talk about inverted indexes, they are almost always term -> posting list, and most index data structures lay these out so that posting lists are sorted and compressed together. Traditional database indexes like B-trees are optimized for rapid insertion and deletion, while inverted indexes tend to be optimized for batch processing, because you typically deconstruct text into words for a large batch and then lazily integrate this batch into the main index.

Part of this is about scale; a row in a database typically has a single column or maybe 2-3 columns in a composite index; but a document text may tokenize into thousands, hundreds of thousands, or millions of words. At this scale, the fine-grained nature of words mean B-trees aren't as a good a fit.

Another part of it is that inverted indexes aren't for point queries, which is what B-trees are optimized for; you typically search for many words at a time in order to rank your search results by some function like cosine similarity. You rarely want a single posting; you want the union or intersection of many posting sorted by score.

▲

modulovalue 4 days ago | parent [-]

NIT: That's not quite correct if your first statement is meant to imply an equality rather than a subset relation.

The idea of an index is more general, as an index can be built for many different domains. For example, B-trees can index monoidal data and inverted indexes are just an instance of such a monoid that a B-tree can efficiently index.

Furthermore, metric spaces (e.g., levenshtein distance) can also be efficiently indexed using other trees: metric trees. So calling inverted indexes just indexes would be really confusing since string data is not the only kind of data that a database might want to support having efficient indexes for.

▲

atombender 4 days ago | parent [-]

My point is that all indexes are "inverted" in the sense that they map some searchable value to occurrences of said value. That is true even if method of comparison is not strict equality.

▲

giovannibonetti 4 days ago | parent [-]

Most indexes people hear about are like that. However, there are indexes that work the other way around, like Postgres' Block Range Indexes (BRIN). They are mostly useful as skip indexes - for a given block, they have a summary that tells whether some given data may be there.

The trade-off this kind of index makes is that it is more optimized for (batch) writes than the more popular B-Tree indexes, but it is less optimized for reads on the other hand. If the write throughout of a given table is very high, you might want to remove all B-Tree indexes that are not strongly correlated to the insert order and have BRIN indexes instead. Combine it with table partitioning, and you can add B-Tree indexes in the cold partitions, or even migrate them to columnar storage if available (with the Citus extension).

By the way, a few years ago a Bloom BRIN variant was added, not to be confused with Postgres' Bloom indexes which are something else.

	▲	atombender 4 days ago \| parent [-]
		I wouldn't say BRIN indexes are "the other way around"; index structure is still one where data values are looked up to find the area where occurrences exist. "Coarse" indexes like BRIN and ClickHouse's data-skipping indexes are still indexes in a broad sense of serving to narrow down a search.