To be really pedantic about the indexing estimates... pgSQL uses B-trees as default. I don't know how many-way the trees actually are (i.e.
how many pointers do the nodes in the tree at most contain) but considering that most unix filesystems seem to use 4 Kilobyte (or should I
say Kibibyte to be use the official NIST definition...:) ) blocksize as default (i.e. the smallest amount of data that the filesystem will read at a
time) one might assume that M is quite big. If the pointers are stored as 4-byte integers one gets that M could be approx 1024, minus some
overhead. To be really safe let's say M=512. Then the number of disk accesses to find a row in a table of 4 billion records is not
log2(4e9)=32 as Don suggested but rather logM(4e9)=4!! Nice, huh? Of course, I'm no super-hacker and certainly no pgSQL-guru, so I
might just be
rambling...(as usual)...😊
