Алгоритм структуры строганых каталогов

Question

Мне нужно хранить большое количество миллионов файлов на диске. Я хочу использовать структурированную структуру каталогов, поэтому в каталоге будет не более тысячи файлов. Если я использую 3 справочника глубоко, я могу получить миллиард файлов (1000^3).

Моя математика немного ржавая, и я не уверен, что правильная формула, чтобы выяснить, какой каталог будет приземляться файлом, если задан целочисленный ключ для файла.

Например, файл '0010.pdf' будет располагаться в каталоге '0000 \ 0000 \ 0000 \ 0010.pdf'. Файл '2010.pdf' зайдет в '0000 \ 0000 \ 0002 \ 0010.pdf'. Таким образом, структура «{уровень 1} {уровень 2} {уровень 3} {файл} '.

Как я могу математически определить различные уровни? Я ищу формулу. Код C# был бы еще лучше, но я могу получить это из формулы, если это необходимо.

Редактировать

я преобразовал ответ ниже в C# функции.

public static string Shard(long key, string extension, int maxFiles = 1000, int depth = 3) 
{ 
    var parts = new List<string>(); 
    long current = key; 

    for (int i = depth; i > 0; i--) 
    { 
     long q = Convert.ToInt64(Math.Pow(maxFiles, i)); 
     long level = current/q; 

     parts.Add(string.Format("{0:0000}", level)); 

     current = current % q; 
    } 

    parts.Add(string.Format("{0:0000}{1}", current, extension)); 

    string separator = Path.DirectorySeparatorChar.ToString(CultureInfo.InvariantCulture); 
    string path = string.Join(separator, parts); 

    return path; 
} 

Answer 1

Разделите на 1000^3 = 1000000000 (mod by 1000 - ничего не делает), чтобы получить каталог первого уровня.

Разделите на 1000^2 = 1000000, измените на 1000, чтобы получить каталог второго уровня.

Разделите на 1000, mod на 1000, чтобы получить каталог третьего уровня.

Mod by 1000, чтобы получить файл.

Обратите внимание, что это может быть сделано просто с помощью цикла for от 1000^3, делящегося на 1000 на каждом шаге.

Пример:

Input: 123456789012 

123456789012/1000000000  = 123 
123456789012/1000000 % 1000 = 456 
123456789012/1000 % 1000 = 789 
123456789012 % 1000   = 012 

Directory/file: 0123/0456/0789/0012 

Или делает это итеративно:
(удаление % 1000 и изменение количества и моддинг на предыдущей стадии вместо)

Input: 123456789012 

123456789012/1000000000 = 123 
123456789012 % 1000000000 = 456789012 

456789012 /1000000 = 456 
456789012 % 1000000 = 789012 

789012  /1000  = 789 
789012  % 1000  = 012 

Принимая результат каждое деление и итоговый результат мод:

Directory/file: 0123/0456/0789/0012 

Дополнительное примечание:

Вы, вероятно, можно избавиться от одной из цифр на каждом уровне вашей структуры - поскольку у вас есть только 0-999, нет никакого смысла, имеющих 4-х цифр.

Answer 2

Вы описываете 3-х уровневый хэш. Наиболее очевидный способ реализовать это - построить 3 разных алгоритма хэширования, каждый из которых принимает строку и возвращает уникальный номер от 0 до 999 на каждом уровне.

В зависимости от того, насколько велика и насколько равномерно распределены целочисленные значения для каждого файла, вы можете просто использовать тривиальный хеш, если целочисленные значения для каждого файла уникальны и составляют менее миллиарда.

http://en.wikipedia.org/wiki/Hash_function

Если вы спрашиваете, как получитьот 0123,993,456 просто сделать целое деление на 1,000,000.

Вы получаете 993, взяв целое число разделить по модулю 1,0000,000, а затем на 1000 и т.д.

pry 
[1] pry(main)> foo = 123993456 
=> 123993456 
[2] pry(main)> foo/1000000 
=> 123 
[3] pry(main)> foo % 1000000 
=> 993456 
[4] pry(main)> foo % 1000000/1000 
=> 993 
[5] pry(main)> foo % 1000 
=> 456 

Answer 3

Так как вы хотите строку, рассматривать его как строку:

private string MakePath(Int32 key) 
{ 
    // make 9-digit string, pad left with 0 
    string s = n.ToString().PadLeft(9, '0'); 

    // insert backslashes 
    return s.Substring(0, 3) + "\\" + 
      s.Substring(3, 3) + "\\" + 
      s.Substring(6, 3); 
} 

Есть, конечно, более элегантные способы кодирования.