Добрый день
Подскажите как в СУБД решают проблему с уникальным значением поля, которое не является ключевым, причем поле типа int32-int64, то есть в простым массивом счетчиков, или огромным битовым полем не получиться обойтись, наверное самое простое троить либо полноценный индекс на B-дереве, ну либо set на B-дереве, возможно есть структура данных которая быстро (в идеале конечно логарифмически) позволяла бы вставлять, удалять запись и проверять есть ли такая запись ну и естественно минимум потребления по памяти, У меня на входе положительные целые числа, и мне не важен порядок как они будут располагаться внутри структуры, мне не нужен последовательный обход, нужно лишь гарантированно знать что такое число уже было либо его не было, возможно думаю тут можно как то адаптировать DAWG, предполагая что у меня алфавит {0,1} и числа являются "строками" на данном алфавите.
Здравствуйте, SL, Вы писали:
SL>Подскажите как в СУБД решают проблему с уникальным значением поля,
Обычно создают вторичный индекс. CREATE UNIQUE INDEX, однако. Хотя если посмотреть на no-sql — там могут быть варианты...
SL>которое не является ключевым, причем поле типа int32-int64, то есть в простым массивом счетчиков, или огромным битовым полем не получиться обойтись, наверное самое простое троить либо полноценный индекс на B-дереве, ну либо set на B-дереве, возможно есть структура данных которая быстро (в идеале конечно логарифмически) позволяла бы вставлять, удалять запись и проверять есть ли такая запись ну и естественно минимум потребления по памяти, У меня на входе положительные целые числа, и мне не важен порядок как они будут располагаться внутри структуры, мне не нужен последовательный обход, нужно лишь гарантированно знать что такое число уже было либо его не было, возможно думаю тут можно как то адаптировать DAWG, предполагая что у меня алфавит {0,1} и числа являются "строками" на данном алфавите.
Какой максимальный размер? Нужен ли persistence? Нужен ли конкурентный доступ? Можно ли масштабировать на кластер?
В большинстве случаев hash-table самая быстрая и экономная по памяти, тем более тебе не нужно сохранять порядок.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
·>Обычно создают вторичный индекс. CREATE UNIQUE INDEX, однако. Хотя если посмотреть на no-sql — там могут быть варианты...
Да это самое первое что видится для реализации, но потенциально может быть порядка 30-40 таких уникальных полей
·>Какой максимальный размер? Нужен ли persistence? Нужен ли конкурентный доступ? Можно ли масштабировать на кластер?
Размер порядка 10E9 значений, persistence не нужен, конкурентный доступ да в рамках транзакционной модели.
Здравствуйте, SL, Вы писали:
SL>·>Обычно создают вторичный индекс. CREATE UNIQUE INDEX, однако. Хотя если посмотреть на no-sql — там могут быть варианты... SL>Да это самое первое что видится для реализации, но потенциально может быть порядка 30-40 таких уникальных полей
А ты уже пробовал обычные решения? Взять какую-нибудь субд, да запилить тупо индексы? Тот же psql, например, умеет тип индекса hash.
SL>·>Какой максимальный размер? Нужен ли persistence? Нужен ли конкурентный доступ? Можно ли масштабировать на кластер? SL>Размер порядка 10E9 значений, persistence не нужен, конкурентный доступ да в рамках транзакционной модели.
Это вряд ли в память влезет... так что надо диск... реализовать/заюзать какую-нибудь hashtable с Memory Mapped Files.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
