一篇软件算法有关的文章待写

我自己懒得写，有兴趣的人可以写，我把思路放在这里。

我想应该可以作为本科生或者硕士研究生的毕业论文来完成。当然了，如果你是大牛，可以当作一个小作业来做。

与数据库有关

以前知道很久以前有一些专门做排序的公司(王嘉廉创办的国际联合电脑公司早年干的也是这种活)，
当时觉得有点不可思议，就做排序也能开公司。因为那些公司的存在，我还以为数据库的各种操作至少都是线性的，就是说O(N)。
现在因为处理的数据量大了，才知道原来一直是O(logN)，难怪各种事务交易后台都那么慢。比如铁道部的网上订票好慢，
网银支付也是好慢。

关于O(logN)

仅以mysql为例，当然了，如果你使用Hash索引引擎，那么是O(1),而不是O(logN)。

这个文章的开始是展示一下O(logN)的性能，让没有真地意识到这个的人有一个感性的认识。然后再谈解决方案。
我的解决方案是对某些(应该说是很普遍通用的一些)情形，提供一个不超过O(N)复杂性的算法，准确地说达到O(1)。
(或许你知道永动机，我的这个说法好像是要搞一个永动机。其实不是，而是真地能够做到，至少我是这么相信的。)
目前这个现状O(logN)让我有点震惊，因为我在1994年的时候就知道有O(1)这样的解决方案了(我真地不是做梦，
我不记得是从哪一本书上学来的，但是真地不是我自己独创的，如果你是研究算法的，你应该早就知道有这样的算法)，
竟然一直没有被加入到普遍通用的数据库里去。

如果你有兴趣做，那么，首先必须向我证明你有能力做这个事，我才会跟你说我的解决方案。你证明你能力的工作可以
作为这篇文章的前半部分内容。具体事项如下：

#1. 一个表格
table(field1 int, field2 char(10))
index field1 primary key
index field2 not unique

索引引擎使用BTree.

我想对这个表格插入1G行,数据随机生成,但是事先生成好，放在另外一台机器上。
插入过程是通过TCPIP接收这1G行数据，插入到数据库里去。不从硬盘上读取，而是从网络上上来因为现在网络比硬盘快。
不放在同一台机器上为了避免对性能测试的干扰。数据事先生成，是为了重复使用，可以做对比。
preparedStatement。每10000行统计一下插入所使用的时间。
这样就可以画一张图来说明，随着数据的增加，插入速度变慢。

数据库刚开始就分配足够多的空间。就是说每行16B, 一共就是16GB.
所以一开始就分配20GB，然后才开始插入。另外，日志缓存要给足够大，当然了其它mysql参数也调成“最优”了。

这是第一步，光是这个，如果你没有两下子，你也搞不定。关键的是要做到你测得的性能数据反映出插入操作的性能。
而不能是别的很多干扰因素。所以上面说的必须把数据放到另外一台机器上通过网络传来。另外，mysql配置好了。
mysql的文档上说得很清楚，这个插入操作是logN的，如果你得不到logN的图像，说明你测试的结果反映的不是插入的性能，
而是别的。所以你必须把环境配置好，才能得到正确结果。如果你两下半就完成这个了，2个可能，你的机器性能极其棒，
你相当棒。

#2. 看mysql源码，找到如下这些问题的答案。
#A select by field1 的复杂度，O(log(N)),还是O(1)
#B select by field2 的复杂度，O(log(N)),还是O(1)
#C insert (field1, field2) 的复杂度

回答了这些问题，说明你有可能有能力把你做的事与当前世界联系在一起。而且如果你能力好，我希望你未来可以把此文提供的解决
方案加入到mysql数据库里去。就是说提供一个新的索引引擎。

#3. 实现一个基于BTree的供测试用的小数据库仅存储上面提到的那个表格。BTree的实现网上有很多源码，可以直接拿来用，
你也可以自己写。最好跟mysql源码使用的语言一样。有了#2，如果有可能，代码结构最好跟mysql源码相似，
这个虽然不是必须的，但是有助于把新实现的索引引擎移植给mysql用。
但是索引模块必须是比较独立的，以便于替换成本文提供的新索引引擎。

#4. 用自己实现的小数据库，插入原先的1G行，记录测试结果，应该得到同样的一张图。y=log(N)的图。
#5. 我将告诉你我的解决方案，你实现它，还是用你的小数据库，插入原先的1G行，应该得到一张图 y=const.
有了这个解决方案，所有的操作(insert, select, delete, update)都应该几乎是O(1)。

#6. 文章整理好就可以发表。如果你觉得有商业价值，你可以不公开这个算法，只是提供可执行文件供人们测试，以便验证
y=const. 如果你也无所谓，你可以公开这个算法。这样我们就可以期待各种数据库很快就可以提供这个新的索引引擎了。
人们就都可以用上了。我觉得这个算法也不是什么秘密，但是鉴于你有能力做到这一步，或许你也有能力靠提供与这个有关的
服务来盈利，所以我把处置权留给你。我真地不是为了卖关子，如果你没有能力做到这一步，告诉你，对你来说也没有用嘛。
我要的是什么？如果你的文章上也署上我的名字就好了，如果你不愿意，我也无所谓。

我离开学校有第一段时间了，与这些内容有关的词汇也很久都不用了，所以有些词汇使用不是可能很准确，
如果你发现了，请告知，好让我修改一下，多谢了。当然了，如果我勤快一点，我可以去查一下。
不好意思，我懒得去查。