From: MikkelFJ Date: 2003-05-28T06:42:17+09:00 Subject: Re: Binary Tree vs. Hash "Xiangrong Fang" wrote in message news:20030527092309.73C4.XRFANG@hotmail.com... > Hi Mikkel, > > Thanks for the detailed explanations. I have some qusestions regarding > your explain: > > 1. You mentioned B-Tree and binary tree, seems that they are different? In principle they are identical, but differ vastly in implementation. A binary tree has two children, the left has smaller values, the right has larger values. A B-Tree has an array of children such that all values in the leftmost subtree is smaller than all values in the next subtree, etc. In effect a B-Tree is a compressed binary tree. In both cases you have logarithmic search. But if you assume the time is consumed by visiting new nodes and not by visiting values within a single B-Tree node, you get a much faster operation. This assumption is true if you read data from disk. There is a limit of B-Tree node sizes beyond which it takes too long time to visit each key within each node. For disk based B-Trees you usually have about 1000 keys (M=1000). You can also use B-Trees in-memory, but then the node size must reflect the size of the CPU cache. When data is in cache, a very fast scan over the array of keys is more effecient than visiting new nodes. B-Trees are very complicated because a node can have between M / 2 and M keys in a node. If you go above or below you must reorginize the tree, This is efficient, but the implementation has lots of special cases. A B-Tree guarantees that you must at most visit K nodes. K is a small limited value. If K is 3 and you have 1000 keys per node (M=1000), you have K^M = 1G possible keys. That is about all you can address in a 32bit systems. For in-memory operation (M=10), K is significantly larger, but if you consider the realistic size of your dataset, it is still small. The trick you can do to make in memory performance better is to organize you tree so allocation of nodes happen close to related nodes. This gives you benefits in lower level cache and virtual memory. Effectively you a split a larger (M=1000) into several smaller (M=10) nodes. This gives you both good in-memory and on-disk performance. In praxis it is not that easy to manage, but you can do something to make it work reasonably well. Binary trees on the other hand do not have a small limit on the number of nodes that you must visit. Therefore they truly have logarithmic behavior. It's not too bad, it is just not the most efficient way to deal with large datasets. A binary tree requires you to visit a new node for each comparison. Binary trees must be balanced otherwise all data could end up in one subtree (becoming just a linked list). There are several ways to balance binary trees (e.g. red-black trees and splay trees). In any case it solves the problem. > 2. I didn't used any of my own hash algorithm, I just used Ruby's hash, > and used Ruby's PStore to dump it to disk. The memory usage is an > estimation from monitoring the task list in win2k. Do you have any > comments about the efficiency of using Ruby's hash and pstore? My best guess is that PStore would not save more than necessary, so you should expect in-memory to take up more space as I already suggested, but I don't know what it does. Your way of measuring is very crude, but probably fair because this is how the system is actually stressed no matter the theory. > 3. My application is related to using N-GRAM method to cut Chinese text > into words (a Chinese bigram is 4-byte string). Do you have any comments > on which algorithm is better? I'd like to here more about this, in private mail if you prefer. It it appears that you are counting "word" or symbol frequencies and can do this by indexing a pair of symbols as a single 32bit word. This is ideal for the hashtable I have implemented as it does not need to visit any external keys. However, it is not available in Ruby. I can send you the C-Source. I already suggested that this source be made available to Ruby but I don't know how well it fits with Ruby as is. It would be specialized for 32 bit words, not general hashes. I have been working a lot with B-Trees and I think I would choose B-Trees over hash tables because they scale better. B-Trees have a good trade-off. They are easy to have small and easy to have very very large and if they are not the fastest solution, they are always seem to be among the best performers. With B-Trees you can have your data on disk and do efficient lookups without needing to load everything into memory. It is possible to have on-disk hash tables, but in the end you need to do some clever memory mananagement that is going to make it look an awful lot like B-Trees. Also, because the key is 32bit the B-Tree is efficient because it does not need to visit external keys. As soon as you visit external keys the cache benefit of B-Trees goes away. However, I do not recommend that you start implementing B-Trees. They are difficult to implement and difficult to make sure that they work. You may be able to use the datastructures in the Berkeley DB database. I don't know how efficient it would be in you case (it's fast but it is a database after all). Berkeley DB does handle hashes and B-Trees. It can operate in in-memory mode only and I think there is a Ruby interface. Note that Berkeley is free only for non-commerical usage. > I am very interested in your comments > about SkipList, can you expand more? I don't recall exactly why skip-lists are better than binary trees, but they are in any case easy to implement (except efficient node allocation). I can send you an implementation in C if you like. This is only a rough outline according to memory: A skiplist is a sorted linked list of all values. Since it is slow to find a value this way, some nodes both point to the next node as well as to one or more nodes further down the list. In fact a skiplist node has an array of next pointers. All nodes have on next pointer, half the nodes have at least two next pointers. Only one nodes has log(N) next pointers (the head of the list). Two nodes has log(N-1) next pointers, etc. The search happens by looking at the longest jumping link first. If that was too far, you try the next shorter jumping node. Eventually you find a node that has a key that matches or is shorter. You now repeat the process jumping from that node. This goes on until you have a match (or conclude failure). This is a bit simplified as there are a few more cases to consider, but this is generally the idea. In reality the skiplist does not have a perfect distribution of nodes. The number of nodes with a certain number of next links may not be optimal, and the location of these nodes may also not be optimal. The distribution happens statistically, but works pretty well in praxis. A skiplist node thus has an array of pointers. This is not unlike B-Tree nodes, except the concept is radically different. There is no complex balancing or splitting of nodes and the performance is decent. However, you are jumping back and forth between a lot of nodes, so it is not friendly to your CPU cache. Since nodes have vastly different sizes it is difficult to make a fast node allocation scheme (if you choose malloc / new, you have lost the speed competition). > Thanks a lot! You are welcome. Mikkel