03 | 索引：如何用哈希表管理亿级对象？

老师，数据在内存中的连续性，对于该数据的序列化的效率上的性能是如何体现的呢

链表的内存地址不连续，是如何让影响序列化的？老师能具体说一下么

从这篇文章，我能想到以下内容： 1、哈希桶选择素数，这个其实是有科学研究的。不同的数据规模选中不同的哈希桶大小，能够保证数据更均匀。 2、Reids中没有使用红黑树而是使用了跳表skiplist，因为shiplist支持区间查找。 3、哈希算法在数据库的分库分表中也常用到，比如第一次计算哈希值找到对应的数据库。 4、在MySQL数据库中使用B+树做索引，是因为可以减少树的高度，同时也可以使磁盘IO加载按照页方式（一页4K）加载。 这样尽可能的多加载到连续数据到内存进行处理。 5、位图bitmap其实在布隆过滤器中使用的比较多，主要是用于判断一个数据是否存在。核心思想就是内部有几个不同的哈希函数， 映射到不同的bit位。如果同一个数据映射的这些bit位都有值，则可以认为该数据存在。 6、哈希算法经过演化（优化）成一致性哈希算法，在分布式系统中节点故障时迁移数据影响范围比较小，其核心思想是两次哈希运算。 关于思考题，我就举一个我熟悉的场景来分析吧。 之前，我们的监控系统和其他厂商接口，对方抓包分析得出我们会有大量重复消息，导致对方处理压力很大，因此我们需要过滤重复信息。 由于我们需要管理数十万个设备运行，所以我们将这些设备划分为两层管理。 第一层，由于设备是接入最近的控制中心的，因此我们第一层按照控制中心进行管理。 第二层，在同一个控制中心，也会有不同的设备，因此我们按照设备的类型进行第二层维护。 第三层，才是我们真正的设备。所以我基于三层管理设备（可以看成三次哈希索引维护），查找更新的效率大大提高了。 我只能想到这么多，希望也能看看其他大牛们的场景。

1.Redis里的HASH用的是链表法，但是有渐进式Hash的方法进行动态扩容. 对于数据内部的持久化用的是RDB和AOF，所以没有序列化的需求 2.布隆过滤器是Hash的一个应用。真未必真，假一定假。因为有多个hash函数，对于不同的请求判断可能会出现Hash冲突，所以会有真未必真 3. 哈希还可以用在向量检索上.LSH局部敏感哈希是说有一组哈希函数使得两组相近的点具有相同的哈希值 4.分布式上的一致性哈希使得数据扩容更容易。

es的倒排索引，可能更偏应用层一些哈！底层的原理都差不多

老师，请教下使用skiplist来构建索引，以下场景有什么缺陷吗？ 假设一个用户积分表有1亿数据，从数据库中读出来，然后构建skiplist，用户表中的数据有更改时（比如新增、修改、删除）时整条记录的时间戳会发生变化，然后定时去根据时间戳来更新skiplist中的数据。

1, java为什么用链接法，而不用开放地址法？ 2, 哈希函数保留信息那里，电话号码是不应该%一个＞10000的素数？QQ号这个想不明白… 3, 扩容时后台迁移，进行判断来选取新旧哈希表。还是比较模糊，新旧哈希表不会让内存压力增大吗？有没有code可以share下，辅助理解。

很喜欢这种风格的分享，有场景，有优劣势分析，落地关键点，老师能否讲下NoSql里为什么喜欢使用LSM

文中说的msync(它可以按地址及长度来分段刷新),确实经典. 不需要备份后的内容是某一时刻的准确逻辑备份. (先备份的是老时间点数据,后备份的可能是新时间点的数据) 但通过oplog的方式修复哈希表,可以保证数据最终的一致性.

B+树索引，业务场景为Mysql索引，主要好处，减少B树过长，磁盘I/O过多情况，一般为2层-3层，支持范围查询。