Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #8478
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: btree vs binary tree |
| Date | 2018-03-16 15:13 +0000 |
| Organization | PANIX Public Access Internet and UNIX, NYC |
| Message-ID | <p8gmv4$pnq$1@reader2.panix.com> (permalink) |
| References | <p8cu67$bm2$1@news.albasani.net> <f3987261-2105-4273-b43a-9f81870575fd@googlegroups.com> |
In article <f3987261-2105-4273-b43a-9f81870575fd@googlegroups.com>, Chad <cdalten@gmail.com> wrote: >I have no idea. I'm just repyling in order to look cool. So with that.... Lemme know how that works out for you, Chad. >I've seen red black trees implemented in Linux (the kernel?). It's the >area where half the people have either MIT or Berkeley email addresses. >It's also the same area where they refer to the Knuth books and speak >of the golden ratio. Yup. Possibly among other things, the Linux kernel uses an RB-tree to hold the set of VMAs (Virtual Memory Areas) used by a process. That is, the regions of the process's address space that have been mapped, either to hold RAM or refer to a device or file backing store. This makes lookups for handling things like page faults fast Golden-ratio style numbers are sometimes used to control the policy for rebalancing the tree, so as to amortize the cost of doing so across several insertions. Since btrees were mentioned, here's an example of a different approach for a VM system implementation that scales better to large multicore machines: https://people.csail.mit.edu/nickolai/papers/clements-radixvm-2014-08-05.pdf - Dan C.
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
btree vs binary tree Melzzzzz <Melzzzzz@zzzzz.com> - 2018-03-15 04:52 +0000
btree vs binary tree Chad <cdalten@gmail.com> - 2018-03-15 14:27 -0700
Re: btree vs binary tree cross@spitfire.i.gajendra.net (Dan Cross) - 2018-03-16 15:13 +0000
Re: btree vs binary tree "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2018-03-16 21:51 +0800
Re: btree vs binary tree cross@spitfire.i.gajendra.net (Dan Cross) - 2018-03-16 15:06 +0000
Re: btree vs binary tree Melzzzzz <Melzzzzz@zzzzz.com> - 2018-03-16 15:30 +0000
Re: btree vs binary tree cross@spitfire.i.gajendra.net (Dan Cross) - 2018-03-16 18:20 +0000
csiph-web