A Matrix-Indexed Bloom Filter for Flash-Based Key-Value Store

Flash-based key-value store, an important type of NoSQL database, has been widely used to store and query data. Indexing structure is an effective organization of data in the store system, which is one of the key technologies to improve the performance of system insertion and query. On the analysis of the characteristics and shortcomings of current and relevant indexing structure, matrix-indexed Bloom filter (MIBF) for flash-based key-value store is proposed. MIBF is composed of multiple Bloom filter group (MBFG) represented by m×s bits matrix and additional Bloom filter (ABF). The core idea of MIBF is that flash page address of key-value pair is split into multiple bit groups, and MBFG is also divided into multiple groups correspondingly, and each group bits are represented by one group Bloom filter (BF) in MBFG, while the combined value of key and flash page address is inserted into ABF. When an element is queried according to the key, each BF group in MBFG generates a plurality of bit values and combines to generate the flash page address for the key-value pairs. In order to reduce pseudo flash page address generated by the MBFG due to false positive probability, pseudo flash page addresses are filtered out through the ABF, thereby achieving more accurate address location, reducing the number of flash access, and improving the system performance. Compared with previous work, the address location accuracy of MIBF query is improved and the access number of RAM and flash is decreased significantly, which greatly improves the performance of solid state disk (SSD) insertion and query.