【jvm我能讲两小时017】Mysql是如何获取索引所在内存中数据页的?

Mysql是如何获取索引所在内存中数据页的?

哈希表， 利用哈希算法。

哈希算法是一种常见算法， 时间复杂度为O （1） ， 且不只存在于索引中， 每个数据库应用中都存在该数 据库结构。

数据库中一般采用除法散列的方法， 发生碰撞时采用链地址法。

在哈希函数的除法散列法中， 通过取k除以m的余数， 将关键字k映射到m个槽的某一个去， 即哈希函数为：

h(k)=k mod m

InnoDB存储引擎使用哈希算法来对字典进行查找， 其冲突机制采用链表方式， 哈希函数采用除法散列方 式 。对于缓冲池页的哈希表来说， 在缓冲池中的Page页都有一个chain指针， 它指向相同哈希函数值的页。 而对于除法散列， m的取值为略大于2倍的缓冲池页数量的质数 。例如： 当前参数innodb_buffer_pool_size 的大小为10M， 则共有640个16KB的页 。对于缓冲池页内存的哈希表来说， 需要分配640×2=1280个槽 ， 但是由于1280不是质数， 需要取比1280略大的一个质数， 应该是1399， 所以在启动时会分配1399个槽的 哈希表， 用来哈希查询所在缓冲池中的页。

InnoDB存储引擎的表空间都有一个space_id， 用户所要查询的应该是某个表空间的某个连续16KB的页， 即 偏移量offset 。 InnoDB存储引擎将space_id左移20位， 然后加上这个space_id和offset， 即关键字 K=space_id＜＜20+space_id+offset， 然后通过除法散列到各个槽中去。