稠密、非唯一索引的存储浪费问题

稠密、非唯一索引可能导致索引文件在存储空间上的浪费。举个例子,key=’中华民国是华人骄傲’ (多达9个字符)的记录有多少条,为它建立的索引项就有多少条。

有个解决办法是在索引项中为每条相应的记录开辟一个指针。这样key=’中华民国是华人骄傲’的索引项只须维护一份,原大量索引项所占的空间变成大量指针所占的空间。一般来说指针所占空间比较小,所以可以节省不少空间。

但是索引项中增加大量指针会使索引项本身的大小过于膨胀,这会影响索引扫描时的I/O速度(需要读更多block)。为了解决这个问题,我们可以专门使用一块空间集中存放所有索引项的指针集合。

这个在索引和数据之间的指针大集合称为 “bucket” (桶).

搜索引擎中常用的inverted index(倒排索引),由于key的重复率特别高,就会经常使用bucket这种机制.

Leave a Comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.