Arbre negre vermell contra arbre B
Tinc un projecte en el qual he de realitzar operacions de cerca, inserció i supressió ràpides de dades que van des de megabytes fins a terabytes. Havia estat estudiant les estructures de dades darrerament i analitzant-les. En ser específic, vull introduir tres casos i fer-hi preguntes sobre això:
Les dades són molt més que el que pot gestionar la memòria (intervals de mostra en 10-15 terabytes) alhora. En aquest cas, emmagatzemaria l’estructura de dades en un disc.
Les dades són relativament menors en comparació amb la memòria del sistema i, per tant, poden emmagatzemar-se i operar-se a la memòria per obtenir més velocitat.
més que memòria lliure i suposem que és inferior a la mida d’un possible fragment contigu de dades del fitxer de paginació. per tant emmagatzemo l'estructura de dades en un fitxer al disc i faig un mapatge de memòria del fitxer.
Les conclusions que he extret són:
Per al cas 1, hauria d'utilitzar un arbre B per accedir-hi més ràpidament, ja que estalvia. en el retard produït per la rotació del disc
Per al cas 2, hauria d'utilitzar un arbre negre vermell per accedir més ràpidament, ja que les dades són a la memòria i no. d’elements que s’haurien d’escanejar en pitjor cas seria inferior a un que he de fer si faig servir Treballs B
Per al cas 3, tinc dubtes sobre aquest tema, el fitxer de pàgina es troba al disc i utilitza E / S d’OS natives per operar en fitxers, de manera que B Tree hauria de ser una opció millor o un arbre negre vermell?
Vull saber on van les tres conclusions anteriors i on va malament i com puc millorar el rendiment en els tres casos separats.
Estic fent servir el llenguatge C ++, amb un arbre negre vermell i un arbre B, tots dos que he dissenyat des de zero. Estic utilitzant la biblioteca Boost per a l'assignació de fitxers.
Actualització 1 :: Estava llegint aquesta publicació a stackoverflow. Tinc algunes bones idees reals, que em fan sentir que el tipus de comparacions que he fet en els casos pot ser defectuós. Es va publicar un enllaç a la resposta més votada per a la resposta http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html