http://damienkatz.net/2008/09/peek-into-couchdb.html
Damien Katz е програмиста за КочДБ - след неколко години ходене по мъките с ерланг е решил да започне всичко от 0-та но на C++ КочБейз (CoachBase).
По принцип всички тези бози се водят "биг дата" - което ме навежда на мисълта да хвърлиш 1 око и на токио кабинет - един японец ги прави и с годините е започнал от нещо съвсем просто до нещо доста сложно
http://fallabs.com/tokyocabinet/spex-en.html
https://code.google.com/p/high-concurre ... loads/list
(И двата линка ми седят отворени в браузъра, че и на мен ми трябва нещо подобно но нямам твоите ограничения - т.е. реших да ползвам хардуер с линукс)
Общо взето най елегантното решение за сортирани данни на блоково устройство/файл си остава бтрее - ако имаш време да го подкараш ще си решиш проблемите за години напред. Ако си притиснат от срокове и бюджета не е проблем взимай базата на McObjects, те са май най стабилни на този пазар, разбира се има и още няколко фирми но в момента не се сещам за конкретни имена.
За справките които ти трябват навремето бяхме мислили да ползваме нещо което ние го нарекохме "агрегатни индекси" - това е сортирано дърво в което всеки възел има сумирани данните в дълбочина - така като ти трябва да намериш сума на всички редове от индекс до индекс ти трябват само 2 заявки в дървото - т.е. вадиш от сумата на по големия индекс сумата на по малкия и получаваш сумата помежду им
Между другото точно това не съм го виждал никъде като структура данни - а е нещо супер удобно за решаване на този доста често срещан по счетоводни системи проблем - където всеки ред зависи от предния - това и да се убиеш на SQL няма как да стане. Да не ти хрумне случайно да ми патентоваш алгоритъма

Споко, няма... а и не ми върши работа

Лошото е че и тия бози дето препоръчваш също не ми харесаха, в смисъл няма да ги ползвам. Но ти благодаря защото трябваше да се запозная с най-добрите преди да взема решение.

Няма да ги ползвам защото или са твърде големи за нуждите и нито една не е съобразена с условието на задачата. Последното е може би ключа към бараката ако се търси ефективност. Да вземем примерно реализация на едно дръвче. Ако имаш промяна на един ключ на практика трябва да се изчете сектора, да се копира в журнала и след това да се запише новата стойност. Минимум 2 писания на сектор и то ако сам си ги правиш, щото със стандартните файлови системи има поне още един служебен сектор в журнала. По-важното е, че при добавяне/изтриване не се променя само новия ключ ами и може и неговите родители до 9-то коляно докато се балансира дървото. С две думи според мен средно статистически при добавяне/изтриване на индекс се пишат поне 4-5 физически сектора.
Аз си мисля че мога да го сведа до средно 1.1-1.2 сектора

Накратко идеята е проЗт сортиран масив и малко още по-прозти идеи така че като вмъкваш да не се налага местене
Масивът е разположен в поредица от сектори и естествено в рамките на сектора ще има местене. В началото е един сектор, вмъкваш - променя се само тоя сектор. Въпросът е какво става като се напълни... Просто се разделя на две, едната половина остава в оригиналния сектор, другата половина формира нов сектор. При първия сектор е ясно, добавяме втори сектор и всичко е ОК.
За да се налага да местя сектори, нека да ги разделим на групи. Примерно от 256 сектора и нека имат логически номера, които съответстват на подредбата. И нека има една таблица от 256 байта, която казва кой логиски номер на кой физически съответства. Така ако да кажем вмъкна индекс в 2-ри логически сектор и той се напълни - шифтвам само таблицата с един байт надясно след 2-я и освобождавам място
Ако броят на секторите е по-малък от 256 с това се приключва. Иначе ще се наложи да изместя последния сектор към следващата група от сектори. Един вид така ще "балансирам" дървото си...

Нека да приемем най-тежката ситуация - да кажем голям ключ, примерно 12 байта +4 байта указател, т.е. в един сектор ще са 30-на индекса. Нека да се пише само един и същ ключ. Средно статистически на всеки 15 записа ще се налага да деля сектора на две. Тогава се пише по стария, по новия и по виртуалната таблица. Демек на 15 записа ще имам 14+3 промени по сектори (ако не броим журнала). И така докато се напълнят всичките 256 сектора.
Мисля си че преносът на сектори от група в група мога да ги избегна ако бозата е малка, или поне да го правя в свободното време, т.е. като станат 250 сектора и няма друга дейност последния ще го местя...

Сега, така или иначе секторите ми ще са с виртуални адрес, мисля да пооптимизирам и малко джурнала... Нормално журнала може да се направи с кръгов буфер, стига във всеки сектор да се отдели място за ревизията му. Тъй като ревизията постоянно расте, кръговия буфер е сортиран и съвсем лесно се стига до сектора с последна ревизия... Аз освен ревизия мисля да имам и CRC за да знам дали е валиден, както и битче да знам дали е последен в транзакция. Така при тръгване се търси последното писане в журнала, гледа се дали е ОК иначе се игнорира.
Та въпросът е как да се съчетае журнала с индексите. Ами просто трябва да се гарантира че има поне 2 празни сектора в групичката, естествено може и повече... Когато трябва да се промени някой сектор той се пише на мястото на празния, старото копие си остава. За да не се променя всеки път виртуалната таблица, корекциите мога да ги пиша в новия сектор ако има място. Нали секторите ми по принцип ще са наполовина празни

Тъй де, ще го обмисля още малко... но се надявам че промените ще могат да се правят много по-бързо, отколкото разните там дървета и хешове... А пък търсенето си е пак двоично търсене, ако не броим няколкото прочетени сектора в началото докато се получи таблицата, ама то при тръгване така или иначе се чеква журнала...

Това което описваш е кажи речи бтрее - само че с едно ниво дълбочина
Може да изродиш дървото до линкед лист - това доста ще упрости нещата, и ще работи доста по ефективно до 3-4 сектора, но от там нагоре дървото по си струва.
При бтрее идеята е точно такава - страниците се държат наполовина празни за да може да добавиш/махнеш елемент в някое листо без да разбутваш цялата йерархия то руут-а. Когато някоя страница се напълни, се цепи на две. Ако две съседни страници имат общ брой на елементите по малък отколкото в една страница се обединяват. Аз май го бях направил да се обединяват когато даден сектор е 30% пълен.
За да паснат нещата със спецификата на СД картата, може да се вкарат няколко дребни но съществени промени.
- в един сектор да не държиш винаги елементите сортирани по ключ, ами по ред на вкарване - така на практика само дописваш в сектора, а го сортираш когато го прочетеш - т.е. идеята е да не се налага при всяко вкарване на елемент да пишеш в журнал
- триенето на елемент също може да става с сваляне само на бит/байт някъде в хедъра
Всъщност това което ти обяснявам май по се вързва когато директно си свързал НАНД/НОР флаш - в твоя случай със СД карта нещата са по лесни защото нейния контролер има грижата да се оправя с презаписи и форматиране (малко на изуст говоря, нямам опит със СД карти на ниско ниво).
А относно линковете които ти пратих - всъщност не са чак толкова големи като компилиран код, по трудоемкото е да ги разгледаш и промениш, така че да ти свършат работа - това си е почти равносилно да си напишеш сам нещата.

за съжаление SD картите не работят така, макар че всъщност никой не може да ти каже как точно работят

И на мен много ми се иска да можеше да се сваля едно единствено битче, както и да се дописва сектор но никой не ти дава подобни гаранции. Зависи какъв wear алгоритъм ползват, зависи предполагам от още един куп неща...
Затова единственото правило, на което разчитам е че като се пипне един сектор няма да се омаже друг. То даже и това никой не ми го е гарантирал, но чисто логически ако това не е изпълнено аз просто нямам никакво решение. Иначе пипнеш ли един сектор, дори само за един бит нямам гаранция че няма да го загубя целия. Де да знам какво е направил китаеца отдолу, пък и както казах тия неща не са стандартизирани и всеки се спасява поединично...

Ако ти трябва надеждност за дълго време, може би СД карта не е най доброто решение. Не, че няма да работи, ми не е гарантирано какво точно ще се случи след 2-3 години с данните.
Само да вметна един детайл относно бтрее-то - навремето като го правих за себе си не ми хареса как се държат данните по страниците в йерархията и го промених да ми пасне повече на концепцията - същинските данни се държат само в листата, а в по горните нива на дървото има само указатели към по долното ниво. Така на практика листата са един голям свързан сортиран списък - точно като това което ти обясни.

ми да... те концепциите се припокриват донякъде.
б-трито е малко по-универсално в случай че не знаш дали бозата ще е от 10 или 100000000 записа. Но пък трябва да се запази и стандартната реализация може би, защото ти като почнеш да го ограничаваш се получава същото като при мен, даже и малко по-зле. На най-ниското ниво ако са само листа се получава напълно идентично. На следващото ниво обаче зависи... Ако слагаш ключове може да спестиш слизане надолу, но пък и ключа и указателя заемат място, докато при мен виртуалната таблица на един блок е само един байт. А на още по-горно ниво пък ми е делението на групи от по сектори. Най-вероятно тия две нива ще ги кеширам винаги в RAM и няма да ми бавят търсенето.
От друга страна б-трито също може да кешира руут-а си. Поне при мен RAM-та е ограничена и е неразумно да кеширам повече от 1-2 KB, така че ако е дръвче ще е само рута. Така с дръвче в RAM-а ще имам инфо за примерно 30-на сектора от следващото ниво, докато с виртуалната таблица ще имам за около 500 сектора при същия размер на кеша. За съжаление обаче това че имам адресите на секторите май няма да ми ускори търсенето... В най-лошия случай пак ще имам log N...
Мдаа... дървото май ще е по-бързо, особено ако е балансирано, а ключовете са неравномерно разпределени. Само че пък балансирането пък е малко по-тегаво и като цяло сложността май ще е малко по-голяма. Шибана работа

Шибана я, почти никой не се занимава с такива неща на толкова ниско ниво. Гугле мълчи като наказан и показва едни и същи академични публикации на някакви китайци/тайванци от които не може да се разбере нищо смислено.

А по нивата имах ключове, нямах данни - т.е. данните бяха указателя към по долното ниво - т.е. структурата беше нещо от сорта:
struct node_link
{
page_ptr_t child_page;
key_t first_key;
};

struct node
{
node_header_t header;
node_link links[PAGE_SIZE/sizeof(node_link)];
};

struct key_value
{
key_t key;
value_t value;
};

struct leaf
{
leaf_header_t header;
key_value data[PAGE_SIZE/sizeof(key_value)];
};

Нищо сложно както виждаш - към това има 2-3 рекурсивни функции за вмъкване/изтриване и търсене. Изправих го на крака за под седмица доколкото помня ('96-'97) и естествено чистих дребни бъгчета година две след това
Та това което ми хареса тогава е точно балансираноста на дървото, скороста за добавяне/махане без да се налага да се разбутва целия файл. Скороста на търсене е ясна - логаритъм от броя на указателите в даден сектор - т.е. МНОГО бързо + много малките изисквания към РАМ-а - все пак имах лимит от 640к за програма + данни - а да навреш в това ГУИ + ДБ + бизнес логика си е бая зор. Е, накрая направихме всичко с овърлеи и ДОС-овското EXE стана 3-4 мегабайта - т.е. нон стоп свапване на овърлеите.
Да се върна на темата: ако добавянето на елементи е рядко - т.е. запис на всеки няколко секунди или по рядко, тогава не ти трявба да кешираш нищо - спокойно може да се оправи всичко една две страници в паметта.
ЕДИТ: Роот-а е просто една страница от тип node чийто адрес се знае - при мен беше в началото на файла, в КочДБ е накрая, което е много по тарикатско както писах - имаш транзакции + машина на времето.