Loading
0

像红迪网(Reddit)这样的巨头网站是怎么如此快速地核实一个新用户名没有被使用过呢?

为了致敬红迪网,我会尽量给出精简的回答,让即使没有涉猎编程和计算机科学概念的行外人也能够理解。

 

首要的重要技巧是红迪网把所有用户名按字母顺序排列储存在数据库中,就是像a, aa, aaa, aaab ……xyzzyx, yishan, zz, zztop 这样按字母顺序排列.这张列表内容十分巨大,有大概八百万个用户名。这些用户名被排列得像字典里的单词。

 

当你输入一个新用户名,这个新用户名会被拿来与这个列表中间的用户名核对,这个中间的用户名就像有调制调节器一样,它会把输入的新用户名与中间的名字对比,并且产生询问:这两个名字相同吗?如果相同,就拒绝新用户名的使用。如果不同,它又会产生询问:这个新用户名按字母顺序是在列表的前半部分还是后半部分呢(以列表中间的用户名为分隔点)?

 

如果计算机判断是在前半部分,那么这个列表后半部分的四百万个用户名都不会与新用户名相同。也就是说,这个系统通过一次比较就排除了四百万个可能。如果是在列表的后半部分,那么系统就会知道前半部分的四百万个用户名都不会与新用户名相同。无论是哪一种情况,我们都通过仅仅一次处理就排除了列表中一半的用户名,而这些都是因为我们做了数据存储。

 

接下来,我们来处理没有被排除的剩下来的一半列表,找到剩余列表中中间的那个用户名,再把它与新用户名比较。和前面的处理过程一样,如果发现它不是完美的匹配(即部分匹配,表示这个用户名可能已经被使用),我们可以分辨出这个新用户名应该在到前半部分还是后半部分中查找(如果这个新用户名真的已经存在的话)。像我们之前做的那样,我们又排除了整个剩余列表中的一半。

 

 

我们每做一次比较就筛选掉掉列表的一半,所以我们可以快速的筛选八百万用户名的列表。你问有多快?

 

也就是说“要把八百万每次分成两半直到最后用户名只剩下一个,要处理多少次?”我们正在尝试把储存列表每次减掉一半直到剩下的用户名的数量足够小,以至于我们可以只得到两个用户名,这两个用户名彼此相邻,然后我们可以将新用户名来跟这两个用户名逐一比较,如果新用户名跟这两个用户名中的任何一个相匹配了,那么说明这个用户名已经被使用了;如果两个用户名中没有与新用户名相匹配的,那么这个新用户名就是有效的。

 

上述问题中处理的次数答案是23次。

 

就是这样。因为我们将用户名都储存在排序表中,我们最多只需要23次比较就可以核实新输入的用户名没有被使用过。这种方法比八百万次的比较快了不知多少倍。

 

如果你想了解更多,你可以看一下这里的其他答案,有的答案解释了这种排序表为什么被称作"索引",解释了这种查找方法和比较过程(或者与这种过程类似的处理方式)是在存储用户名的数据库中提供的,还有一些其他细节。

 

(authentic author:Yishan Wong)

 

 

原网址:

https://www.quora.com/How-do-giant-sites-like-Reddit-verify-that-a-username-isnt-taken-so-fast/answer/Yishan-Wong?share=15d06f58&srid=hUOw9