一种基于字段使用频率的索引选择模型及算法实现
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于字段使用频率的索引选择模型及算法实现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：本文基于SQL Server 2000数据库，通过对索引开销的研究，针对如何建立最适当索引的问题给出索引选择模型以及相应算法，并比较各算法的优劣，确定最优选择
关键词：数据库；索引选择；字段使用频率；遗传算法
中图分类号：TP311 文献标识码：A文章编号：1007-9599 (2011) 12-0000-02
Index Selection Mode and Algorithm Realization Based on Filed Use Frequency
Liao Bin
（Guangxi College of Education,Nanning530023,China）
Abstract:Based on SQL Server 2000,focus on how to create the most proper indexes,and gives the index selection model and the corresponding algorithm through the research of index spending.Then compare the pros and cons of each algorithm to determine the optimal choice.
Keywords:Database;Index Selection;Filed Use Frequency;Genetic Algorithm
对于数据库的设计者，总会面临这样的问题：索引的建立一方面能提高数据库存取效率，另一方面索引本身也需要有额外的时间和空间开销。如何尽可能地取得索引建立的最佳效果，在实际的数据库系统中，可根据各字段的使用频率来建立索引选择模型，得出益评价公式[1]。在字段Fi上建立索引的得益可表示为：
（1-1）
其中：
，为字段 作为查询关键词时所节省的查询费用；
，为字段作为连接关键词时的最少节省费用；
，为字段建立索引所产生的费用；
，表示采用B树索引结构的树高。
由得益公式可知，若要建立索引，应选取得益 的字段 。然而，实际的系统中只能提供有限的空间来建立索引文件，所以在哪些字段上建立索引必须用算法来最终确定。
二、索引选择模型算法实现
由索引得益公式，当某个字段的得益 时，不考虑在其上建立索引。假设得益 ，系统可用于建立索引的空间大小为s， （ ）表示在字段 上建立索引需要的磁盘空间，则选择索引应满足[2]：
（2-1）
同时还应该使系统得益最大，所以问题的实质是求向量 ，使得：在满足 的情况下，获得最大的价值V，即：
（2-2）
显然这属于0-1规划问题[3]，可通过穷举法、贪婪算法、遗传算法分别来对0-1规划问题进行求解。
三、算法的比较
设物体个数n、物体重量W、物体收益P和背包容量C。取C=1000，n=50。对W和P任意各取50组数据。
（一）算法时间开销
物体个数取值以及上述三种算法求解所用时间曲线图如图1所示：
图1.算法时间比较曲线图
由上可得各算法时间消耗的比较结果：
1.贪婪算法耗时最短，几乎为零，执行效率最高。
2.当考查数据个数较少（
3.当考查数据个数逐渐增多（>20），穷举法的执行时间迅速地趋向于无穷大；遗传算法执行时间平缓增加，仍然保持在秒级别。
（二）算法解的优劣
取每种算法的解 与最优解 之间差值 ，通过（ ）%来考查算法解的优劣情况，穷举算法的解即为最优解。得出算法解优劣曲线图2，直观反映每种算法解的优秀情况。
图2.算法解优劣曲线图
其中遗传算法在数据量较少时，总能得到最优解，具有很快的收敛速度。当数据量增加，收敛速度降低，得到的为近似解。对于遗传算法的近似解，均是经过多次（>10）运算求解后，取其中偏差最大的近似解。可以看出，遗传算法最差近似解和最优解的差值与最优解之比保持在2%以内，结果与其它两种算法相比更为优秀。
因此，当0-1背包问题具有交大规模的数据并且对结果的要求较高时，遗传算法在计算的复杂度和解的优秀度上取得了一个较好的平衡，是一种更为先进适用的算法。
四、索引选择测试结果分析
以North wind数据库为例，单位时间内出现一次查询，查询内容为订单号、产品编号、产品名称、顾客、地址、城市、联系电话、数量及单价，涉及到的表为Products、Orders、Order Details、Customers，不发生插入及删除操作。
通过算式（1-1）以及相应的算法实现，可得有收益的，适合建立索引的字段组合为A。此外，取任意字段组合B、C、D、E作为对比。可见，在有收益的字段上建立索引，查询速度有明显提高。从相应的查询成本也可以看到，在有收益的字段上建立索引后，查询的开销最少；反之，查询的开销将会增加，从而导致查询速度的降低。如图3、图4所示：
图3.索引查询时间示意图
图4.索引查询成本示意图
五、结论
通过对实例数据库的应用，对索引选择模型及相应算法的正确性进行了验证。验证显示，在由索引选择模型筛选出的字段上建立索引，能够有效地减少数据库查询的开销，提高查询的效率。此外，通过对遗传算法的应用，在对较大规模的字段进行组合选择时，能够迅速地得出最优或者接近最优的结果，极大方便了数据库索引的选择设计。
参考文献：
[1]颜启华,方美凤.索引对查询开销影响的研究[J].华南师范大学学报(自然科学版),2004,2:52-55
[2]于红,王秀坤.基于SQL Server的索引选择模型[J].小型微型计算机系统,2003,2:243-245
[3]李北斗.关于0-1背包问题的算法研究[J].计算机与数字工程,2008,5:23-26