maytonТогда я разочарован. Я просто искал структуру данных или хранения данных которая
позволяла-бы работать с таблицей так как будто у нее все поля всегда проиндексированы.

Мне казалось что это достижимо для CODBMS

поясни - что и зачем ты хочешь делать по индексу (номеру/итератору) -
а) обращаться к полю в строке таблицы или
б) обращаться по номеру к конкретной строке таблицы
в) что-то третье (вычитывать подряд данные строк с 5 по 50 принадлежащие к 17-му столбцу)

Для реляционной теории первое не возбраняется (технически описание элементов отношения именами и уникальными номерами, имеющими характер атрибутов множества, эквивалентно ).
С практической точки зрения, климентские интерфейсы типа odbc естественным образом допускают обращение к элементам (полям) полученного набора данных по номерам.
, а второе с точки зрения теории не имеет смысла.
В практическом плане самые простые системы работы с данными вроде данных в формате dbf-III
естественным путем обеспечивают работу со строками по номерам.

Разница между строчным и колоночным хранением примерно такая - в первом случае некая непрерывная область памяти содержит набор строк, во втором случае непрерывная область памяти содержит данные одного столбца, относящиеся к множеству строк таблицы.

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

А если из таблицы на 125 полей и триллион строк всегда выбирается лишь пара полей (узкая проекция широкой таблицы),
то в порядки раз быстрее два раза пробежаться по двум непрерывным областям хранения значений полей (вау -= параллельно пробежаться) чем перемолачивать гигатонны террабайт игнорируемых столбцов при строчном хранении.
В таком случае игнорируемые столбцы просто не будут прочитаны и потому не смогут создать никакой нагрузки фактом своего существования.
Зато Select * для column store - это простая, примитивного сорта (то есть - невыразимая словами) боль .

А зато если в лоб хранить column store в файлах по числу столбцов, да на каждый из них натравить zip, то ого-го какую экономию можно получить в размере базы данных, по сравнению со строчным хранением (говорят, что при инмемори компрешн втрое лучше
сжимать столбцами, чем строками), из-за однородности данных (дни рождения с днями рождения, сексуальные принадлежности с
сексуальными принадлежностями, коды территорий рядком с кодами территорий и т.п.)

Думаю, что для любого случая конкретной таблицы потребуется ее описатель, включающий в себя описатель полей (словарь полей)
(или набор описателей - если ты захочешь на уровне определения таблицы иметь множественное описание - именами и метками номеров (имена другого сорта - другой системы, с которыми при доп. договоренности можно обращаться как с числами).
Дальше, для строчного хранения, потребуется указатель на область памяти, с которой начинается хранилище строк.
Детали устройства строки на твое усмотрение - обязана она быть фиксированной длины или нет (если что-то чуть более "продвинутое" , чем dbf - то длину строки не фиксируют. Имеет право хотя бы иногда быть фрагментированной - то есть занимать несколько непрерывных диапазонов внутри логически сплошной области хранения строк или нет и т.д.

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

Если разглядывать Землю невооруженным глазом с границ Солнечной Системы, то примерно как-то так.
А по мере приближения к Земле, число различимых звездочек имеет право увеличиваться - сначала 3, потом 5.
Т.е. - детали всех алгоритмов - выборки, проекции и соединения не совпадают и специфичны для своего "способа хранения".

ps1
Прошу извинить за участие в топике - про C++ я в практическом плане ничего не знаю.

Ps2
не знаю что сейчас в базвордах по поводу колумн сторе.
Лет 10 назад было правильно гуглить по словам C-Store или MonetDB или Sybase IQ.
А сейчас какую только чертовщину этим словом не назовут.

booby,
прошу простить опечатки.

mayton,

мне кажется, что я приблизительно почувствовал, чего ты ищешь.
так же мне кажется, что в этом деле есть перпендикуляр.
то есть в наборе твоих суждений стоят как заходы, в которых ты скорее прав, так и заходы, в которых ты по вероятности не прав на текущий момент.
да, копаниями, рубаниями, отсечениями, дерзаниями и терзаниями на перпендикулярах что-то интересное создается.
в диковатой озвучке - некий всепольный супер-индекс как универсальная структура произвольного доступа по произвольно взятой комбинации полей.
также мне понятно, почему ты готов пожертвовать ценой восстановления экземпляра строки ради скорости поиска.
это да - column store специфически для этого, но !не для oltp! на сегодня.
типичный oltp это однострочный select -> update/insert -> comit
column store пытается выиграть на первой фазе, откровенно наплевав на вторую и третью.
что для oltp полностью неприемлемо.
column store и позиционируется и фактически применяется для data warehouse, где в online нет ни update/insert ни коммит.
сломать это может только волшебство, внезапно хотя бы приближающее insert/update/commit к временам, характерным для строчного хранения.

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

mayton...Или БД в которой не будет потребности индексировать столбцы.
вероятно it's doable в каком-то виде.
во первых - внутри индекс-организованных полей структура совмещена - строки хранятся прямо в структуре индекса,
во вторых, если не идет речь многопользовательском варианте и совместном доступе, то первое, что приходит в голову
- некий граф поверх bitmap полей, кодирующих конечный словарный набор значений как разширение идеи индекс-организованной таблицы.

booby,
внутри индекс-организованных полей таблиц

mayton,

погугли (дополнительно к индекс-организованным таблицам) "oracle bitmap index structure"
что-нибудь вроде доки или здесь посмотри - www.juliandyke.com/Presentations/BitmapIndexInternals.pp

bitmap-индекс это попытка обеспечить быстрый доступ (в том числе по комбинации) для полей, у которых набор значений в домене мал, а число строк, хранящих эти значения - огромно, путем кодирования в битмап-полях идентификаторов строк, в которых появляется то или иное значение/комбинация.
В части скорости доступа к по настоящему большим наборам данных при строчном хранении - штука фантастическая, в обмен на жертвы в части совместной доступности таблиц для изменений и сжирание процессора до степени каления.
во всяких, близких по объемам к настоящим, хранилищах поверх oracle database без этого вантуза не живут

mayton,
про восстановление, похоже, ты меня неправильно понял - я не про логи, восстановление и целостность говорил совсем.
вот твоя колоночная таблица
coedbmsTable:
name[Varchar2(100)] = {Маша,Вася, Вася, Петя, Федя, Ира, Паша, Витя, Саша, Галя, Валя}
age[Number(3)] = {10 ,40 ,65 , 34 , 25 , 42 , 38 , 56 , 57 , 18 , 31 }

вот запрос:
select name,age from coedbmsTable where age between 10 and 30

вот результат, который вернул твой поиск:
name[Varchar2(100)] = {Маша, Федя, Галя}
age[Number(3)] = {10 , 25 , 18 }

а клиенту, ты хочешь (можешь хотеть) отдать
{{name, age}
{Маша, 10},
{Федя, 25},
{Галя, 18}
}

то есть преобразовать результат из колоночного преставления в вариант строчного.
то есть восстановить строки из колонок - в этом смысле.
и в этой логике нет никаких хранимых идентификаторов строк.
------------------------------
- по поводу остального
ты говоришь примерно следующее (я так тебя понимаю):
1) индекс позволяет а) осуществить поиск значения строки за логарифмическое время и б) автоматически поддерживают сортировку по возрастанию-убыванию значений. гут - хочу - пусть у меня хранение каждой колонки будет в виде индексного дерева.
т.е. если в базе два Васи и одна Маша, то получится что-то такое
{Вася:32CEA158B6D90409E0530820A8C012BB, Вася:32CEA158B6D90409E0530820A8C013BB,
Маша:32CEA158B6D90409E0530820A8C011BB}
или такое
{Вася:{32CEA158B6D90409E0530820A8C012BB,32CEA158B6D90409E0530820A8C013BB},
Маша:32CEA158B6D90409E0530820A8C011BB}
здесь Васю сжали для экономии места, но без задействования битмап-карт

2) тогда сама таблица выродится в набор идентификаторов строк (rid/rowid/"номеров_строк" - guid), к которым и будут привязаны
хранимые в индексе значения,а хранить его тоже в индексе, чтобы быстро добираться до идентификатора строки по его значению.

3) а чтобы восстановить строку по условию name='Maша' (Маша - уникальна) я полезу в столбец name
и по ключу 'Маша' отыщу хранимый в индексе идентификатор строки, найду в индексе
{'Маша:32CEA158B6D90409E0530820A8C011BB'},
далее, т.к. просили меня Select *, то используя уже '32CEA158B6D90409E0530820A8C011BB' я полезу в индексы, обратные к
виду {ключ=значение_поля, значение = идентификатор строки таблицы}
индексирующие сами идентификаторы строк, вида
{{32CEA158B6D90409E0530820A8C011BB:10}}, каждый из которых будет уникальным.
В простом случае даже можно себе представить что такой "обратный", "восстанавливающий" индекс - один - общий на все столбцы.
и имеет вид
{{32CEA158B6D90409E0530820A8C011BB:{name='Маша',age=10}}
(но это есть строчное представление в конечном счете)
Т.е. в такой системе хранимые значения задвоятся, а идентификаторы строк размножатся по числу полей.

битмап здесь при том, что число имен людей и и мощность множества их возрастов, выраженная в годах,
много меньше числа людей и может появиться желание перейти к более компактному представлению по отношению даже к сжатому
Вася:{32CEA158B6D90409E0530820A8C012BB,32CEA158B6D90409E0530820A8C013BB}
фиксируя местоположения идентификаторов встречающихся строк с именем Вася в некоторой битовой карте представляющей
разом все множество наличных строк.

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

как-то так я увидел твои намерения.
И задачу сформулировал бы так:

Можно ли придумать такую систему хранения (вероятно - граф некоего сорта),
которая была бы быстрой на поиске как b-tree индекс и универсальной по отношению к выбранному набору полей для которого
формулируется условие поиска. Для начала - безотносительно к сложности модификации данных на такой структуре.

Не знаю, на сколько это идея удачна, но, может быть, есть смысл посмотреть в сторону алгоритмов поиска на строках.
Подразумевая, что хранимая строка данных это буквально строка и ставится задача сопоставления против множества образцов.
Такой Ахо-Корасик, вживленный в инмемори субд.
(Деревья для таких поисков желательно простроить их начала)

Еще раз сорри - я не для поучать, а так - на поговорить заскочил, пока коньячок согревается.
А так мне менять позицию надо - вот уже и аромат из бокала выпирать начал - пора.


Для начала без учета проблемы модификации

booby,

авторТакой Ахо-Корасик, вживленный в инмемори субд.
впрочем, больше на на regexp похоже

mayton...
Пока дошел до того что нужен merge двух R/B деревьев. Или поддеревьев.

А как ты планируешь мержить свои деревья, если узел одного из них указывает на экземпляр значения 'Вася', а узел другого указывает на экземпляр значения '10'.
Карл, на что должен указывать узел дерева, полученного как результат слияния первых двух?