Blog: Latest Entries (9):





vibKeyboard

Mal eine kleine Spielerei, die mir bei der Autofahrt zur Arbeit eingefallen ist. Am Ende hat es ungefähr 20min gedauert die WebApp zuschreiben. Ich werde auch noch mal eine Manifest-Datei für Firefox OS dafür basteln. Aber erstmal geht es auch so ganz gut. Das Alcatel One Touch Fire hat beim Vibrieren leider relativ wenig Wumms, aber auf einem Android Handy kam das Vibrieren etwas besser rüber. Das Samsung Wave 1 mit Bada 2 unterstützt die Vibration-API in JavaScript leider nicht.
Beim drücken der Testen vibriert das Handy für eine gewisse Dauern. Mit rec kann man eine Tastenfolge aufzeichnen und mit play wieder abspielen. Wenn man wieder auf rec drückt wird hinzugefügt. Um das vorherige zu löschen muss man einmal auf new drücken.

vibKeyboard-WebApp


Nested-Sets Alternative

Tree-Strukturen in einer Relationalen-DB:



Alternative zu einfachen Child-Parent Strukturen oder Nested-Sets. Der Vorteil würde darin liegen, dass die Inserts im Vergleich zu Nested-Sets bedeutent schneller sind und dass dabei aber nur wenige Vorteile dabei verloren gehen. Trotzdem sind Änderungen noch immer langsamer und das Problem bei Fehlern die Struktur wieder herzustellen bleibt auch in einem gewissen Rahmen. Im Vergleich zu Nested-Sets kann die Struktur aber nicht bei einfachen Inserts zerstört werden, sondern nur wenn Änderungen innerhalb der vorhandenen Struktur vorgenommen werden und dabei eine Transaktion abbricht. Aber auch hier ist das Rekonsturieren sehr viel einfacher, weil die verbliebenen Einträge vor dem Abbruch meistens ausreichen sollten um die Transaction an der abgebrochenen Stelle wieder aufnehmen
zu können.

Das Prinzip basiert auf einer seperaten Tabelle, die alle Relationen der Nodes untereinander (wenn sie Parent oder
Child sind) beinhaltet.


nodeId | parentId | distance
_______|__________|_________
12 | 1 | 3
12 | 3 | 2
12 | 7 | 1


Der Node mit der Id 12 ist also ein direktes Child von dem Node mit der Id 7. Node 7 ist ein Child von Node 3 und Node 3 ist ein Child von Node 1. Node 1 ist das Root-Element.

Direkte Children von Node 3 erhölt man also wenn parentId=3 ist und distance=1. Den direkten Patren von Node 3 mit nodeId=3 und distance=1. Alle Parent mit nodeId=3 und die Sortierung wird über distance vorgenommen.

Inserts sind auch leichter als man erstmal denkt. Wir fügen an Node 12 eine Zusätzliche Node mit der Id 13 an.

Dafür kopieren wir und den Teil der Table für Node 12 und ersetzen die Id von 12 und erhöhen die distance jeweils um 1. Am Ende fügen wir den fehlenden letzten Eintrag einfach hinzu, da dieser keinerlei Berechnung benötigt.


nodeId | parentId | distance
_______|__________|_________
12->13 | 1 | 3+1
12->13 | 3 | 2+1
12->13 | 7 | 1+1

13 | 12 | 1


damit haben wir alle Einträge für 13 ohne Rekursion oder dem Ändern anderer Einträge vorgenommen.

Auch das Umhängen eines Nodes innerhalb des Trees ist ähnlich benötigt aber etwas Vorarbeit. Wir hängen z.B. Node 7 an Node 4

Es müssen alle Nodes bei denen Node 7 in den parentId's steht aus gelesen werden und aufsteigend nach distance sortiert werden. Nun werden alle Einträge von Node 7 gelöscht und wie beim Insert neu eingetragen. Danach folgen die direkten Children nach dem selben Muster. Deren Eintrag mit der distance 1 verrät immer noch den Parent und solange der bekannt und vorhanden ist, lassen sich die Tabelleneniträge wie beim Insert schnell wieder aufbauen.

Beim löschen eines Node werden auch alle Children entfernt. Da bedeutet alle Nodes bei denen die parentId gleich der Id des zu entfernden Nodes ist. Dabei spielt die distance keine Role, da solche Einträge nur existieren, wenn der Node ein direktes oder indirektes Child ist.

Dieses Verfahren benötigt natürlich mehr Joins auf DB-Ebene. Aber da sind heutige DBs wohl ausreichend schnell für.
Das einzige wirkliche Problem wäre, dass diese Tabelle sehr schnell sehr sehr groß werden würde. Abhängih von der Tiefe des Baumes kann es ohne Probleme dazu kommen, dass die Tabelle 10x so viele Einträge hat wie die eigentliche
Node-Tabelle.

next try

Nach einiger Zeit werde ich mal wieder versuchen etwas aktiver an meiner Homepage zu arbeiten. Neben den JS-Projekten hat sich auch viel am grundlegenden Framework der Seite getan. Mit diesen neuen Versuch veröffentliche ich auch demnächst die Version 0.5, die schneller und auch noch etwas sicherer sein sollte, als die doch schon sehr alte Version, die man hier noch downloaden kann.

Older posts:

Möchtest Du AdSense-Werbung erlauben und mir damit helfen die laufenden Kosten des Blogs tragen zu können?