Talk:Hash tree (persistent data structure)

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

???

This article has not yet received a rating on Wikipedia's content assessment scale.

???

This article has not yet received a rating on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Merge in Hash array mapped trie and Ctrie

Since HAMTs and Ctries are hash trie implemented using particular types of underlying tries, those articles can be merged into this one to get something of an overview article. QVVERTYVS (hm?) 11:26, 15 May 2013 (UTC)[reply]

Well, I would have to strongly disagree on two grounds.

First, although it is true that the design of the ctrie initially began based on the successful HAMT, it was explicit in the goals of the effort, from the outset that the ctrie address a very different use-case that otherwise successful HAMT had been seen to be very unsuitable for. Specifically,HAMT is a persistent immutable functional datastructure, and this type of model, while broadly effective for in-memory (GC supported) applications was very space-inefficient, for example, when applied to situations requiring the structure to be allocated on-disk. The architecture of CTrie diverged to the extent that IMHO it barely recognizable as much similarity at all with that of its forebears. Most importantly, it is a mutable, concurrent index based extensively on the use of atomic CAS and a unique new variant of RDCSS called. GCAS that permitted the implementation to be accomplished using only single compare and swap instruction primitive which are widely ubiquitous on almost all current consumer-grade hardware. I don't have an interest in engaging Ina much longer explication on these fundamental architectural differences, but if you are interested, please have a look at my implementation http://github.com/danlentz/cl-ctrie and I would be happy to debate he matter more fully.

Information on this remarkable structure is extremely sparse, difficult to find, and inconsistent and I am quite certain that a dedicated Wikipedia page on the topic is both appropriate and helpful for those that are looking to learn more about the topic. I, personally, have on many occasion directed people to this page to lean more of the general background during conversations on the matter. It would be tragic to bury it in the HAMT article. — Preceding unsigned comment added by Danlentz (talk • contribs) 14:43, 14 August 2013 (UTC)[reply]

I think we should keep this as a separate article. This data structure is special in the sense that it is the first concurrent, lock-free data structure with efficient, lock-free atomic snapshots that allow creating consistent iterators and performing size operations. — Preceding unsigned comment added by RolandMid (talk) 16:01, 8 February 2014 (UTC)[reply]