Thread: is a database essentially like a big linked list?

  1. #1
    CIS and business major
    Join Date
    Aug 2002
    Posts
    287

    is a database essentially like a big linked list?

    I was reading the book, The Art of Computer Programming, the section on information structures. After reading the section on linked lists, it seems to me that a database is essentially a big linked list. Since a linked list is almost like a linear array that can expand and contract as data is put into and taken out of it, this seems to me like it is just a smaller version of a database.

    Any of you who have programmed a database before may have insight into this question. But I was wondering if a database is just like a big linked list?

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Angola
    Posts
    8,445
    Not really, no. One aspect of databases is random access to any part of a table (row and field), whereas linked lists require you to traverse each node (row) when searching.
    At the most elementary level, a database is perhaps best thought as a group of simple bidimensional arrays, one for each table. But concerning their design they are usually implemented as a combination of data structures like B-trees and hash tables.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,611
    Mario answered sufficiently, but I guess it doesn't hurt to echo him.

    I was reading the book, The Art of Computer Programming, the section on information structures. After reading the section on linked lists, it seems to me that a database is essentially a big linked list. Since a linked list is almost like a linear array that can expand and contract as data is put into and taken out of it, this seems to me like it is just a smaller version of a database.
    I would say databases aren't like linked lists. It really depends on how you look at it, and the more you know about the subject, the less appropriate the comparison seems to be.

    Most data structures will be flexible to accommodate more information, (or less) so it's definitely not something unique to linked lists. Moreover, databases do not have to simply grow linearly, as in inserting or deleting table records. If we are talking about a relational database, it could also grow like a web, as new tables and new relationships are created.

    The truth is that a DBMS needs to be programmed with a number of features in order for us humans to safely work with the database much like a computer would operate on its simpler structures. These are often complex features built out of multiple data structures. One that I would at least try to use if I built my own relational database is the hash table.

    Additionally, we are often interested in things a computer does not necessarily need for its structure. One key difference between, say, a linked list and a database is that a database can be stored in digital files. Once you store many data structures in a file format, they really lose the properties that made them work in RAM.

    HTH.
    Last edited by whiteflags; 11-02-2016 at 05:28 PM.

  4. #4
    CIS and business major
    Join Date
    Aug 2002
    Posts
    287
    Cool, thanks for the responses.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 04-19-2014, 10:01 PM
  2. Replies: 11
    Last Post: 11-09-2012, 12:45 PM
  3. Replies: 2
    Last Post: 11-08-2012, 02:05 AM
  4. Changing static array database system to linked list
    By DLH112 in forum C Programming
    Replies: 13
    Last Post: 12-09-2009, 12:50 PM
  5. Is a queue essentially a linked-list?
    By dudeomanodude in forum C++ Programming
    Replies: 4
    Last Post: 03-17-2008, 07:54 AM

Tags for this Thread