Relace nad KV databází

[Ivan Nový]

Úloha je relační databáze s indexy nad (vybranými) sloupci...

To jsi vyčetl kde?

Pojem relační implikuje hledání podle indexů. Když nevíš, jak se to implementuje, tak kušuj (to platí pro všechny trolly).

Relační neimplikuje hledání podle indexů, relace nemusí být setříděná, a ani setřídění v dané relaci nemusí vůbec dávat smysl. Relační databáze jsou relační proto, že využívají k zachycení reality relace, tedy ne nutně uspořádané soubory uspořádaných entic. Indexy jsou tam navíc, souvisí s praktickou implementací, klidně by mohly být realizovány hardwarově asociativní pamětí, nebo neuronovou sítí.

[Reklama]

[zboj]

Už několikrát jsem při čtení o databazích narazil na zmínku, že relační databáze jde postavit nad KV úložištěm, ale nepodařilo se mi vygooglit nic bližšího. Jak se tabulky ukládají, když jsou k dispozici jen klíče?

To jde jen tehdy, když jsou klíče v úložišti setříděné.

Jak se teda dělá uložení záznamu a hledání v indexu?

Každé pole záznamu má klíč tabulka:uid:pole. Pro načtení záznamu stačí použít dolní mez tabulka:uid: k iteraci přes všechna pole záznamu. Indexy mají klíč index:pole:hodnota a jako hodnotu seznam uid. Pro vyhledání se pak použije dolní mez index:pole:hodnota. Stěžejní je schopnost úložiště nalézt nejbližšího následníka podle lexikografického uspořádání. Taková implementace je optimální (lépe to nejde) a typicky se používá něco jak B+ strom, aby vyhledání bylo vždy O(log n).

[gll]

Zboj zas píše o něčem co nezná.

tabulku reprezentuji dvojicemi primarni_klic radek. Některé databáze podporují víc klíčů pro jednu hodnotu, tam není co řešit. V ostatních lze odkazovat přes primární klíč. Klíče pro jednotlivé sloupce mohu odlišovat prefixy, nebo je ukládat do zvláštní datové struktury.

[zboj]

Úloha je relační databáze s indexy nad (vybranými) sloupci...

To jsi vyčetl kde?

Pojem relační implikuje hledání podle indexů. Když nevíš, jak se to implementuje, tak kušuj (to platí pro všechny trolly).

Relační neimplikuje hledání podle indexů, relace nemusí být setříděná, a ani setřídění v dané relaci nemusí vůbec dávat smysl. Relační databáze jsou relační proto, že využívají k zachycení reality relace, tedy ne nutně uspořádané soubory uspořádaných entic. Indexy jsou tam navíc, souvisí s praktickou implementací, klidně by mohly být realizovány hardwarově asociativní pamětí, nebo neuronovou sítí.

Nebo kvantovým algoritmem

[Kit]

Úloha je relační databáze s indexy nad (vybranými) sloupci...

To jsi vyčetl kde?

Pojem relační implikuje hledání podle indexů. Když nevíš, jak se to implementuje, tak kušuj (to platí pro všechny trolly).

Kdybys napsal, že chceš relační databázi s indexy, tak bych ti byl poradil. Denně používám několik typů relačních databází. Některé s indexy a některé bez nich. Uvedená implikace neplatí.

Pokud potřebuješ indexy, použij místo KV databáze raději relační. Bude s tím méně práce. Bývá na každém hostingu (i těch zdarma) a můžeš jich tam mít v aplikaci kolik chceš.

[Reklama]

[Kit]

Relační neimplikuje hledání podle indexů, relace nemusí být setříděná, a ani setřídění v dané relaci nemusí vůbec dávat smysl. Relační databáze jsou relační proto, že využívají k zachycení reality relace, tedy ne nutně uspořádané soubory uspořádaných entic. Indexy jsou tam navíc, souvisí s praktickou implementací, klidně by mohly být realizovány hardwarově asociativní pamětí, nebo neuronovou sítí.

Nebo kvantovým algoritmem

Ten je možné použít také, ale většinou si v takových případech vystačíme s fuzzy logikou.

[Filip Jirsák]

Pojem relační implikuje hledání podle indexů. Když nevíš, jak se to implementuje, tak kušuj (to platí pro všechny trolly).

Nikoli. Pojem ,,relační databáze" je založený na matematických relacích a znamená, že máte data reprezentovaná v tabulkách (relacích), přičemž všechny řádky tabulky mají stejné sloupce. S indexy to nemá vůbec nic společného. Tabulka relační databáze je například i následující seznam osob s datem narození:

• Eliška, Malá, 19. 3. 1986
• Jan, Novák, 13. 6. 2001
• Tamara, Brzobohatá, 17. 12. 1967

V KV databázi to vyjádříte tak, že jednotlivé řádky uložíte třeba jako hodnoty s vnitřní strukturou, nebo do hodnot LV databáze uložíte jednotlivé hodnoty (hodnotu atributu pro daný záznam), ale strukturovaný bude klíč (třeba ID_záznamu.ID_atributu).

[gll]

Stěžejní je schopnost úložiště nalézt nejbližšího následníka podle lexikografického uspořádání. Taková implementace je optimální (lépe to nejde) a typicky se používá něco jak B+ strom, aby vyhledání bylo vždy O(log n).

https://redis.io/commands/scan

"Time complexity: O(1) for every call."

[kimec]

Stěžejní je schopnost úložiště nalézt nejbližšího následníka podle lexikografického uspořádání. Taková implementace je optimální (lépe to nejde) a typicky se používá něco jak B+ strom, aby vyhledání bylo vždy O(log n).

https://redis.io/commands/scan

"Time complexity: O(1) for every call."

Prave ste poukazali na fakt, ze Redis drzi kluce v hash tabulke a nie v B+strome. Preto si rad pozriem ako vam SCAN bude vracat "nejbližšího následníka podle lexikografického uspořádání".

Vasu argumentaciu ste mohli postavit aj na prikaze ZSCAN, ale ani to by vam nepomohlo, kedze implementacia v Redise pouziva skip listy a INSERT a REMOVE su spoplatnene komplexitou O(log n). Predpokladam, ze pre search kluca pre zaciatok iteracie pouzije hash.

Nehovoriac o tom, ze Redis je in-memory store. Co v pripade, ak mate tolko klucov, ze sa vam cela hash tabulka (+ dalsie podporne struktury v pripade Sorted sets) a hodnoty nevojdu do pamate?

[zboj]

Stěžejní je schopnost úložiště nalézt nejbližšího následníka podle lexikografického uspořádání. Taková implementace je optimální (lépe to nejde) a typicky se používá něco jak B+ strom, aby vyhledání bylo vždy O(log n).

https://redis.io/commands/scan

"Time complexity: O(1) for every call."

Prave ste poukazali na fakt, ze Redis drzi kluce v hash tabulke a nie v B+strome. Preto si rad pozriem ako vam SCAN bude vracat "nejbližšího následníka podle lexikografického uspořádání".

To bych taky rád viděl. Spíš ten osel ukázal na fakt, že absolutně neví, o čem se tu bavíme.

[Kit]

Nehovoriac o tom, ze Redis je in-memory store. Co v pripade, ak mate tolko klucov, ze sa vam cela hash tabulka (+ dalsie podporne struktury v pripade Sorted sets) a hodnoty nevojdu do pamate?

V takovém případě se obvykle přidá paměť nebo se neklíčové atributy uloží do souborového systému. V Redisu se pak uchovávají jen klíčové položky a URL.

[kimec]

Už několikrát jsem při čtení o databazích narazil na zmínku, že relační databáze jde postavit nad KV úložištěm, ale nepodařilo se mi vygooglit nic bližšího. Jak se tabulky ukládají, když jsou k dispozici jen klíče?

Pre uplnost, presny priklad vasej definicie je Apache Phoenix , t.j. relacna databaza nad KV uloziskom.

KV ulozisko je v tomto pripade HBase s jedinym indexom podla vzostupne radenych rowkey. Phoenix vyuziva HBase koprocesory a custom filtre pri skenovani klucov tak, aby vycaroval pocit relacnosti. Zaujimave su secondary indexy, ktore generuje tiez cez koprocesory a to tak, ze obsahuju celu strukturu stlpcov a data z primarnej tabulky, takze pri skene cez secondary index pouzije data rovno z indexu. Ano, vnizkaju tam duplicity. Ale to predsa pri Big Data nie je problem.