2 ms·
One question. Isn't this how B+ Tree index on a column work? A BT index is just the sorted values of a column with pointers to the row id of the actually rows
by ww520 15y ago
One question. Isn't this how B+ Tree index on a column work? A BT index is just the sorted values of a column with pointers to the row id of the actually rows. Note that BT index are often compressed as well since the sorted values have many similarity to its neighbors.
Also what's the difference between the bitmap part and the Bitmap Index (http://en.wikipedia.org/wiki/Bitmap_index http://en.wikipedia.org/wiki/Bitmap_index)?
- jorgeleo 15y agoThe difference is in the operations. With a b tree the software operates on 1 row at a time, but when represented as a series of bit, then in a 32 bit CPU you can process 32 rows in 1 instruction. Which leads to bitmap index over GPU...
- nivertech 15y agoIt will be 64bit at a time using plain CPU instruction or 128-512bits at a time using SIMD or GPU. Also article describes a word-aligned bitmaps data structure, which uses RLE, so it will skip areas of all-zeros or all-ones.
- jorgeleo 15y agoYes, the only problem I found when writing my own bitmap index is they become cumbersome when asking the question: what value has this column for this row. RLE does not help there. But they are extremely fast when asking the question: what rows has this value on this column. And that is the whole concept, the ability to flip the question.