Ivkin I
Въведение.
Един от основните проблеми при съхраняването на толкова голям брой файлове е необходимостта от интензивна работа с тях. В случай, че тези файлове постоянно се изискват за преместване, актуализиране, изтриване или добавяне на нови файлове, натоварването на файловата система се увеличава драстично. Първо, трябва постоянно да актуализирате файловата таблица, второ, фрагментацията се увеличава и трето, свободно място на устройството се губи. По-скоро тясно място е предварително разпределеният размер на клъстера във файловата система. В случай, че има много файлове и те са толкова малки, че не надвишават размера на клъстера (например 32 килобайта), режийните разходи за тяхното съхранение могат да бъдат сравними с общия размер на съхраняваните данни.
Определение на изходните данни.
Броят на файловете трябва да е достатъчно голям. Много съвременни файлови системи използват специфично изпълнение на файлова таблица (която е база данни), която съхранява информация за съдържанието на томове на външно устройство за съхранение. Например във файловата система NTFS тази функция се изпълнява от MFT - Главна файлова таблица - в нея редовете съответстват на файловете за обем, а колоните съответстват на атрибутите на файла. При значителен брой файлове броят на записите в тази таблица става толкова голям, че забавя работата с файловата система. В хода на практическата работа беше разкрито, че когато се използва файловата система NTFS, работата значително се забавя с няколкостотин милиона файла. Следователно необходимият брой файлове за съхранение трябва да надвишава 200 милиона и да бъде ограничен до приблизително 1 милиард файла.
Проектиране на структура от данни за съхранение на файлове.
Тази стратегия за съхранение се нарича произволно съхранение. Стратегията за случайно съхранение по правило има доста висока ефективност при вмъкване на нови данни; тя се оценява като O (1). В същото време има проблем с потенциално ниско време за извличане, но този проблем се решава чрез използване на индекси.
Размерът на съхранените данни не е задължителен. В този случай ще е необходимо да се прочетат данните до първата срещана последователност от байтове, която условно ще се нарича "разделител". Този метод е допустим, но експериментът показва, че в този случай производителността на четене леко намалява, тъй като данните трябва да се четат на малки порции и за всяка порция е необходимо да се провери дали е открит разделителят. Следователно за всеки запис в индекса е необходимо да се съхраняват данни като отместването спрямо началото на файла и размера на съхранените данни.
Съхранението на отместването като брой байтове от началото на файла е неефективно поради следните причини. В случай, че 32-битово неподписано цяло число се използва като контейнер за тази стойност, максимално възможната стойност може да бъде само 2 32 или 4 гигабайта данни. Това е сравнително малък размер на данните, който бързо ще бъде надвишен, ако има голям брой файлове. Следователно ще е необходимо да се използва 64-битово цяло число, което веднага води до необходимостта да се съхраняват 8 байта за всяко отместване от началото на файла. Лесно е да се изчисли, че за един милион файлове разходите за съхраняване на информация за компенсации ще бъдат приблизително равни на 8 мегабайта, а за сто милиона - 800 мегабайта. Това потребление на памет е неефективно, така че трябва да изберете различен индикатор.