使用内部数据结构作为内存数据库是否是一种好方法

Question

我正在开发一个非常小规模的程序，主要致力于使用单词首字母来搜索完整的字符串和附加的额外信息，包括程序内 CRUD 操作。由于只有 ~10k 个字符串可供搜索，因此我更喜欢使用内存中方法来加快搜索速度（因为大多数查询都是SELECT ）。

简单地使用像List<myobject> data这样的东西并做这样的事情是一个好方法：data.Where((s => s.text.Substring(0,3) == expected));？使用此方法时，我可以对数据库优化（如索引）做些什么？

Answer 1

TL;DR
我建议评估您的要求。如果使用简单的List<>满足您的要求，并且您对分析应用程序的性能结果感到满意，请使用它。如果没有，请考虑使用内存数据库。

---

数据库足够快以检索数据的主要原因之一是索引。使用常见的 C# 数据结构时，会错过此功能。我认为如果您正在处理少量记录，那么您不会遇到性能问题，但是如果您有很多记录，那么您应该考虑在内存数据库中使用。请记住，所选数据库可能不支持您希望为数据编制索引的方式，或者您有复杂的查询，索引不会提高其性能。

如果你只有键和相应的值，那么看看Redis和StackExchange.Redis。

要考虑的另一件事是并发性！数据库通常支持从多个线程访问数据，并处理同一数据的多个读取器或写入器。可以在 .NET 中使用线程安全集合，但必须执行大量操作才能获取数据库中内置的功能。

Answer 2

如果您只进行前缀搜索（如问题中所示），您可能可以使用列表，只要您保持排序并进行二叉搜索而不是线性搜索（这是where将要做的）。

字典虽然在进行精确匹配时要快得多，但在这里不是正确的工具，因为您想进行仍然是 O（N） 的搜索。

如果要使用 LINQ，最好只使用 EF 和 SQL Server CE。这是一个非常轻松的选择，尽管您显然添加了一些重要的依赖项。

如果你想在C#中推出自己的解决方案，它的工作方式与数据库几乎相同，你正在寻找的数据结构被称为Trie[1]，这仍然不会给你LINQ（除非你写更多的代码），但会给你很好的搜索性能。

[1]https://en.wikipedia.org/wiki/Trie

Answer 3

如果您使用的是数据结构，那么最好使用复杂度为 o（1） 的数据结构，如字典和哈希表，而不是复杂度较慢的列表。请注意，该列表正在占用一些空闲内存。

Answer 4

检查此测试：

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace CSharpConsoleApplication.Tests
{
    class JustATest
    {
        public static void Run()
        {
            var list = new List<Test>();
            for (int i = 0; i < 1000000; i++)
                list.Add(new Test() { Text = "a" + i.ToString().PadLeft(6, '0') });

            string input = "a011";
            List<Test> found = null;


            // Get the results with LinQ
            var w = new Stopwatch(); w.Start();
            found = list.Where(t => t.Text.Substring(0, 4) == input).ToList();
            w.Stop();
            Console.WriteLine("Search list with linq. Results count = {0}", found.Count);
            Console.WriteLine(w.Elapsed);
            Console.ReadLine();


            // Store data in dictionary if no refresh needed
            // Populate the dictionary
            var objectsDictionary = new Dictionary<string, List<Test>>();
            w.Restart();
            PopulateDictionary(objectsDictionary, list, input.Length);
            w.Stop();
            Console.WriteLine("Populate dictionary");
            Console.WriteLine(w.Elapsed);
            Console.ReadLine();
            // Search in dictionary
            w.Restart();
            if (objectsDictionary.ContainsKey(input))
                found = objectsDictionary[input];
            //objectsDictionary[input].ForEach(t => Console.WriteLine(t.Text));
            w.Stop();
            Console.WriteLine("Search in dictionary. Results count = {0}", found.Count);
            Console.WriteLine(w.Elapsed);
            Console.ReadLine();
        }
        static void PopulateDictionary(Dictionary<string, List<Test>> dictionary, List<Test> list, int textLength)
        {
            foreach (var t in list)
            {
                string text = t.Text.Substring(0, textLength);
                if (dictionary.ContainsKey(text))
                    dictionary[text].Add(t);
                else
                    dictionary.Add(text, new List<Test>() { t });
            }
        }
        class Test
        {
            public string Text { get; set; }
        }
    }
}