This document is a cache from http://www.nobius.org/~dbg/practical-file-system-design.pdf

Practical File System Design

Document source : www.nobius.org

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 All Pages

78
5
AT T R I B U T E S , I N D E X I N G , A N D Q U E R I E S
cat
man
train
acme
buck
deluxe
indigo
navel
style
able
ball
deft
edge
mean
rowdy
Root node
Figure 5-4 An example B-tree.
Knowing that B-tree nodes are sorted and the links for each entry point
to nodes with keys less than the current key, we can perform a search of
the B-tree. Normally searching each node uses a binary search, but we will
illustrate using a sequential search to simplify the discussion. If we wanted to
find the word deft we would start at the root node and search through its keys
for the word deft. The first key, cat, is less than deft, so we continue. The
word deft is less than man, so we know it is not in this node. The word man
node (deluxe indigo) we compare deft against deluxe. Again, deft is less than
deluxe
, so we follow the associated link. The final node we reach contains
the word deft, and our search is successful. Had we searched for the word
depend
, we would have followed the link from deluxe and discovered that
our key was greater than deft, and thus we would have stopped the search
because we reached a leaf node and our key was greater than all the keys in
the node.
The important part to observe about the search algorithm is how few nodes
we needed to look at to do the search (3 out of 10 nodes). When there are
many thousands of nodes, the savings is enormous. When a B-tree is well
balanced, as in the above example, the time it takes to search a tree of N keys
is proportional to log
k
(N). The base of the logarithm, k, is the number of keys
per node. This is a very good search time when there are many keys and is
the primary reason that B-trees are popular as an indexing technique.
The key to the performance of B-trees is that they maintain a reasonable
balance. An important property of B-trees is that no one branch of the tree
is significantly taller than any other branch. Maintaining this property is
a requirement of the insertion and deletion operations, which makes their
implementation much more complex than the search operation.
Insertion into a B-tree first locates the desired insertion position (by doing
a search operation), and then it attempts to insert the key. If inserting the key
would cause the node to become overfull (each node has a fixed maximum
size), then the node is split into two nodes, each getting half of the keys.
Splitting a node requires modifications to the parent nodes of the node that
Practical File System Design:The Be File System
, Dominic Giampaolo
page 78

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 All Pages

Summary :