索引学习笔记
-
用哈希表来实现索引。
-
考虑这个数据库表 user，我们需要检索 id=4 的数据，SQL 语法是：select * from user where id=4;
-
用哈希算法，先计算这个id=4的hash值，假设hash(4)=4231
-
4231直接映射到这行数据所在磁盘文件指针 0x77。
-
哈希算法有个碰撞问题
-
不同的数据算出来的hash值可能一样
-
比如hash(7)可能跟 hash(199)一样
-
映射到的磁盘文件指针也一样。
-
解决碰撞问题：链地址法。用链表把碰撞的数据连接起来。
遍历这个链表，然后比较hash值
找出 id>3 的数据
全表扫描