A Quaint Discrepancy between My Dated Meaning of ‘Index’, and the Current Meaning

I actually became acquainted with computers, doing a data-entry job, on a long-forgotten database management system, on a long-forgotten PC. According to what I remember, a database consisted of a main table of records, each of which had a fixed set of fields, plus any number of Index Tables. Each record in the main table had a record number, which was only meaningful to the one DBMS. Each index table consisted of the values of one particular field of the main table’s records, sorted, and each associated with one main table record number, in which the value of the indexed field occurred.

This meant that if a look-up needed to be performed according to which up to 3 fields had a defined value, notionally, the first of those 3 fields could be looked up in its index table, while the additional 2 fields would have been considered to occur in random order, and their legitimacy determined through comparisons, that all resulted from the look-up of the first field, in its index table.

Today, an index is said to refer to something else. If the blocks in a database have a block-number, then the main table is thought of as a kind of ‘array of blocks’. The index, or block-number, is the index of this array.

Dirk

 

Something that might count Against FAT32

One fact which In have written about, is that each File System essentially has a different way, of organizing the Blocks on an HD, or on an SSD, into Files, and of managing free storage space.

One fact which they all seem to have in common however, is that HD or SSD Blocks possess ‘Logical Block Addresses’, aka LBAs. What this means in simplified terms, is that every Block on an HD has a unique Block-Number, which can be used to point to it, very much the way in which Pointers do, to addresses in RAM. There can be some differences though, in whether the Physical Blocks correspond directly to Logical Blocks, mainly because a given HD platter might have a Physical Block Size of 512 Bytes, while the O/S might require that Logical Blocks have a size, compatible with the size of Pages, of Virtual Memory. Since Virtual Memory Pages are usually 4KB, this would seem to imply that 1 Logical Block always corresponds to 8 Physical Blocks, and that any file will take up space, corresponding to at least 1 Logical Block, regardless of where the logical end of the data is, inside its last Block.

One way in which a File System can allocate Blocks to a File, is just by chaining them, and this can make for an entertaining way to explain Computing. I.e., at the beginning of each allocated Block, there could be a Header, which among other things, states an LBA which points to a ‘Next Block’ in a chain, or which is otherwise Null to state that the current block is also the last one, belonging to a File.

The use of such header information that resides inside the Physical Blocks, that are supposed to contain data and not meta-data, has a major drawback though. It can be accommodated by a modern O/S with some effort, but again causes the Physical Blocks, not to correspond directly to Virtual Memory Pages, since some odd number of Bytes have to be subtracted from their size then, to arrive at the size of units of data and not meta-data, which then also does not correspond to a clean power of two.

I think that ‘FAT32′ uses such an approach.

Because a modern O/S has such features as Memory-Mapped Files and Virtual Memory, its performance would take a considerable hit, if it was forced to use the old ‘FAT32′ system – as its main store of system data.

What tends to happen with up-to-date File Systems, is that Logical Blocks that are mapped directly from HD Physical Blocks – Contain only Data, and contain no Meta-Data. ‘Unix System V’ was an early example of that; therefore ‘ext2′, ‘ext3′, ‘reiserfs’, and ‘ext4′ are examples of that as well. The way in which these File Systems keep track of Blocks as belonging to Files, is through one ‘iNode’ per File, plus an arbitrary number of Index Tables, the latter of which each contain one Logical Block of Meta-Data, consisting entirely of the LBAs, of data-blocks, that belong contiguously to any one File.

So there are entire pages of meta-data, stored on these higher-performing File Systems, and many of them. If that becomes corrupted, the effect is not the same, as when regular content-data becomes corrupted.

‘NTFS’ also possesses Index Tables, but I think replaces the use of ‘iNodes’ by Linux, with a ‘Master File Table’. LBAs are used as pointers throughout. Whether other people will think that a Master File Table is more secure than the use of many iNodes is, I do not know. I feel more secure with a system of iNodes.

The iNode or the MFT will state as part of their meta-data, the exact length of the File, in Bytes, so that the FS does not read past its end, even if the end of the content-data is midway through a Logical Block.

Dirk