哈希表如何工作？它比"SELECT*from ..."更快

Question

比方说,我有:

Key | Indexes | Key-values
----+---------+------------
001 | 100001  | Alex
002 | 100002  | Micheal
003 | 100003  | Daniel

可以说,我们想搜索001,如何使用哈希表进行快速搜索过程？

是不是和我们在mysql中使用"SELECT*from .."一样？他们说,从头到尾搜索"SELECT*"很多,但哈希表不是吗？为什么以及如何？

通过使用哈希表,我们是否减少了我们正在搜索的记录？怎么样？

任何人都可以演示如何在mysql查询代码中插入和检索哈希表进程？例如,

SELECT * from table1 where hash_value="bla" ...

另一种情况:如果索引类似于S0001,S0002,T0001,T0002等.在mysql中我可以使用:

SELECT * from table WHERE value = S*

是不是一样快？

Answer 1

一个简单的哈希表通过将项保存在多个列表而不是一个列表上来工作.它使用非常快速且可重复(即非随机)的方法来选择保留每个项目的列表.因此,当需要再次找到该项时,它会重复该方法以发现要查找的列表,然后在该列表中执行正常(慢速)线性搜索.

通过将项目划分为17个列表,搜索速度提高了17倍,这是一个很好的改进.

虽然当然只有列表的长度大致相同才有效,所以选择一种在列表之间分配项目的好方法很重要.

在您的示例表中,第一列是键,我们需要找到该项.我们假设我们将维护17个列表.要插入内容,我们对名为hashing的键执行操作.这只是将键变成一个数字.它不返回随机数,因为它必须始终为同一个键返回相同的数字.但与此同时,这些数字必须"广泛传播".

然后我们得到结果数并使用模数将其缩小到我们列表的大小:

Hash(key) % 17

这一切都发生得非常快.我们的列表是一个数组,所以:

_lists[Hash(key % 17)].Add(record);

然后,使用该键找到项目:

Record found = _lists[Hash(key % 17)].Find(key);

请注意,每个列表可以是任何容器类型,也可以是您手动编写的链接列表类.当我们Find在该列表中执行a 时,它的工作方式很慢(检查每条记录的键).

Answer 2

不用担心 MySQL 内部如何快速定位记录。数据库的工作就是为你做这类事情。只需运行一个SELECT [columns] FROM table WHERE [condition];查询，然后让数据库为您生成一个查询计划。请注意，您不想使用SELECT *，因为如果您向表中添加一列，这将破坏所有依赖于按特定顺序存在一定数量的列的旧查询。

如果您确实想知道幕后发生了什么（知道是件好事，但不要自己实现：这就是数据库的目的！），您需要知道索引是什么以及它们如何工作。如果一个表在 WHERE 子句中涉及的列上没有索引，那么，正如您所说，数据库将必须搜索表中的每一行以查找与您的条件匹配的行。但如果有索引，数据库将搜索索引以找到所需行的确切位置，并直接跳转到它们。索引通常以B+ 树的形式实现，这是一种搜索树，使用很少的比较来定位特定元素。在 B 树中搜索特定键的速度非常快。MySQL 还能够使用哈希索引，但这些索引对于数据库使用来说往往速度较慢。哈希索引通常只在长键（尤其是字符串）上表现良好，因为它们将键的大小减少到固定的哈希大小。对于整数和实数等具有明确定义的排序和固定长度的数据类型，B 树的易于搜索性通常会提供更好的性能。

您可能想查看MySQL 手册和PostgreSQL 手册中有关索引的章节。